\documentclass[11pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{lmodern,amsmath,amssymb,amsthm,mathtools,booktabs,enumitem,microtype,needspace}
\usepackage[a4paper,hmargin=23mm,vmargin=25mm]{geometry}
\usepackage{tikz}
\usetikzlibrary{positioning}
\usepackage{xcolor}
\usepackage{hyperref}
\hypersetup{pdftitle={A nonlinear connectivity code larger than every linear code},pdfauthor={Matěj Kripner, Václav Rozhoň, Robert Šámal, Martin Šindelář, Adrián Zámečník}}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{question}[theorem]{Question}
\newtheorem{example}[theorem]{Example}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newcommand{\F}{\mathbb F}
\newcommand{\Clin}{m_{\mathrm{lin}}}
\newcommand{\D}{\mathcal D}
\title{A nonlinear connectivity code larger than every linear code\thanks{This work was produced within the Bolzano project (\url{https://bolzano.app}), using AI systems for mathematical research and manuscript preparation. The listed authors contributed to the project and the preparation of this release. The manuscript received only limited human checking.}}
\author{Mat\v{e}j Kripner \qquad V\'aclav Rozho\v{n} \qquad Robert \v{S}\'amal\\[0.4em]
Martin \v{S}indel\'a\v{r} \qquad Adri\'an Z\'ame\v{c}n\'ik}
\date{}

% Collection typography; mathematical statements and proofs are unchanged.
\definecolor{BolzanoInk}{HTML}{24445C}
\hypersetup{colorlinks=true,linkcolor=BolzanoInk,citecolor=BolzanoInk,
  urlcolor=BolzanoInk,pdfauthor={Matěj Kripner, Václav Rozhoň, Robert Šámal, Martin Šindelář, Adrián Zámečník},pdflang={en-US}}
\urlstyle{same}
\setlength{\emergencystretch}{1em}
\let\BolzanoBibliography\thebibliography
\renewcommand{\thebibliography}[1]{\BolzanoBibliography{#1}\raggedright}
\begin{document}
\maketitle
\begin{abstract}
A connectivity code on a graph $H$ is a family of edge sets of $H$ whose pairwise symmetric differences are connected spanning subgraphs. Alon asked whether a nonlinear connectivity code can ever be larger than every linear one on the same graph. We answer this affirmatively: we construct a $4$-regular graph on fifteen vertices on which the largest connectivity code has nine members and the largest linear connectivity code has eight. The code is obtained by lifting a quaternary code of length six with pairwise agreement one through clique gadgets.
\end{abstract}

\section{Introduction}
\subsection{Background and the source problem}
Classical minimum-distance conditions control how many coordinates distinguish two codewords. Graph codes instead prescribe the \emph{shape} of the difference: when codewords are edge sets of a graph, one may require that any two of them differ in a spanning tree, a Hamiltonian cycle, a triangle, or some other structure. This point of view was developed by Alon, Gujgiczer, K\"orner, Milojevi\'c, and Simonyi~\cite{AGKMS} and by Alon~\cite{GraphCodes}; Alon's survey~\cite{Survey} gives a broad account. Connectivity is the most basic structural requirement, since it asks that the difference cross every nontrivial vertex cut.

Let $H=(V,E)$ be a finite simple graph. Edge sets are identified with vectors in $\F_2^E$, and vector addition is symmetric difference, denoted by $\triangle$.
\begin{definition}[Connectivity codes; Alon \cite{Alon}]
A family $\mathcal C\subseteq 2^E$ is a \emph{connectivity code} if $(V,A\triangle B)$ is connected for any distinct $A,B\in\mathcal C$. It is \emph{linear} if it is a vector subspace of $\F_2^E$. Write $m(H)$ for the maximum size of a connectivity code and $\Clin(H)$ for the maximum size of a linear one.
\end{definition}
Every codeword is regarded as a spanning subgraph, even if its edge set is empty. Connectivity is required of differences, not of individual codewords. Translating every codeword by one fixed edge set preserves all differences, so a code can always be normalized to contain the empty set.

Restricting a connectivity code to the edges of a nontrivial cut is injective, since otherwise some difference misses that cut. Hence $m(H)\leq 2^{\lambda(H)}$, where $\lambda(H)$ is the edge connectivity~\cite[Section~1]{Alon}; for $d$-regular $H$ this gives $m(H)\le 2^d$. In each of the following exact results the optimum is attained by a linear code. For the complete graph, $m(K_n)=2^{n-1}$~\cite[Theorem~1]{AGKMS}, attained by the cut space of $K_n$. Bai, Gao, Ma, and Wu show $m(C_3\mathbin\square C_3)=16$~\cite{BGMW}, where $\square$ denotes the Cartesian product. Alon proves that every $d$-regular graph satisfying a mild cut-expansion hypothesis has a linear code of size $2^d$~\cite[Theorem~1.1 and its proof]{Alon}, and Tian recently showed that for every $d\ge 4$ there is a $d$-regular graph with $m(H)=2^d$~\cite{Tian}, again via linear codes. This motivates the following question.

Alon \cite[Section 4, second concluding remark]{Alon} asks whether nonlinear connectivity codes can be larger than linear codes on the same graph, and Tian \cite[Section 6(c)]{Tian} repeats the question, noting that his constructions are linear. In precise form:
\begin{question}\label{q:source}
Is there a finite simple graph $H$ for which $m(H)>\Clin(H)$?
\end{question}
The question asks for a strict separation on a single graph; it does not prescribe an asymptotic ratio or a graph family.

\subsection{Main result}
The graph has disjoint cliques $U_i=\{a_i,b_i,c_i,d_i\}$ and hubs $h_i$, for $i\in\mathbb Z/3\mathbb Z$. In addition to every edge inside each $U_i$, include
\begin{equation}\label{eq:graph}
 h_i a_i,\quad h_i b_i,\quad h_{i+1}c_i,\quad h_{i+1}d_i
 \qquad(i=0,1,2),
\end{equation}
and no other edges. Denote the resulting graph by $G$.
\begin{theorem}\label{thm:main}
The graph $G$ in~\eqref{eq:graph} is simple and $4$-regular, has fifteen vertices and thirty edges, and satisfies
\[
 m(G)=9>8=\Clin(G).
\]
A nine-member code in $G$ can contain the empty edge set.
\end{theorem}
Theorem~\ref{thm:main} answers Question~\ref{q:source} affirmatively and determines both optima exactly. Since a linear code has power-of-two size, any code of size nine already separates; the content of the theorem is that nine is attainable in $G$ and ten is not. We also show (Proposition~\ref{prop:order}) that fifteen vertices is the least order of a separating example within the doubled-six-cycle framework used here; smaller separating graphs outside that framework are not excluded.

\subsection{Related work}
\emph{Graph codes with structured differences.} Alon, Gujgiczer, K\"orner, Milojevi\'c, and Simonyi~\cite{AGKMS} study families of graphs on $[n]$ whose pairwise differences are connected, $k$-connected, Hamiltonian, contain a spanning star, and so on, and they determine $m(K_n)$. Bai, Gao, Ma, and Wu~\cite{BGMW} study how the maximum size changes as the class of admissible differences varies, establishing several phase transitions, and compute the torus value quoted above. Gishboliner, Jin, and Sudakov~\cite{GJS} solve a further problem from~\cite{AGKMS}, determining the largest family of graphs on $[n]$ in which any two members have isomorphic differences. Alon~\cite{Alon} introduced connectivity codes on a fixed host graph and proved the expander theorem; Tian~\cite{Tian} completed the determination of the maximum over $d$-regular hosts.

\emph{Forbidden differences and intersecting families.} A dual family of problems forbids a structure in the difference. Alon~\cite{GraphCodes} considers families of graphs on $[n]$ in which no difference is a copy of a fixed graph $F$ together with isolated vertices, and Versteegen~\cite{Versteegen} proves upper bounds for linear such codes; his introduction discusses whether linear codes may be optimal in that setting. These problems are closely related to intersecting families of graphs: Ellis, Filmus, and Friedgut~\cite{EFF} proved the Simonovits--S\'os conjecture that a triangle-intersecting family of graphs on $[n]$ has at most $2^{\binom n2-3}$ members, and Berger and Zhao~\cite{BergerZhao} proved the analogous statement for $K_4$. Theorem~\ref{thm:main} shows that, for connectivity codes on a fixed host, linear codes need not be optimal.

\emph{Linear versus nonlinear codes.} In classical coding theory it has long been known that nonlinearity can pay. The Nordstrom--Robinson code~\cite{NR} is a binary code of length $15$ with $256$ codewords and minimum distance $5$, twice the size of the best binary linear code with the same parameters; this and the Kerdock and Preparata families were later explained as Gray-map images of linear codes over $\mathbb Z/4\mathbb Z$~\cite{HKCSS}. The present construction is similarly driven by a code over a four-letter alphabet, although here the alphabet records pairs of edge indicators, and the obstruction to linearity is just the power-of-two cardinality.

\emph{Counting.} The upper bound $m(G)\le 9$ is a Plotkin-type double count~\cite[Theorem~1]{Plotkin}: projected words over a four-letter alphabet must agree in at most one of six positions, and ten such words would create at least $48$ coordinate agreements among only $45$ pairs.

\subsection{Proof overview}
Contracting each clique $U_i$ leaves a six-cycle alternating between clique parts and hubs, with two external edges at every cycle position; see Figure~\ref{fig:quotient}. A connected difference can miss at most one position. The auxiliary words record the two edge indicators at each position as one of four symbols; their pairwise differences therefore occupy five positions and connect the quotient along a path. The nine words arise from six partitions of the nine points of $\F_3^2$, arranged so that every pair of points shares exactly one block.

The internal edges require a more careful choice. Relabelling the symbols independently in each coordinate makes one distinguished external word zero without changing agreements. The cut space of $K_4$ has eight members, and every nonempty cut is connected and spanning. Assign its eight members bijectively to the other eight word indices, and toggle one fixed edge in each assignment. In a difference between two such indices, the toggled edge cancels, leaving a nonempty cut. This handles all differences except those against the distinguished zero word.

Against zero, the toggle can leave a disconnected internal graph. This is unavoidable: requiring every difference to be connected inside each clique would impose the complete-graph bound $m(K_4)=8$. Instead, the coordinate labels are chosen so that each exceptional internal pattern receives the external edges that reconnect it through its adjacent hubs. Lemma~\ref{lem:repair} lists these repairs, and Theorem~\ref{thm:lift} shows that they assemble globally.

The matching linear construction uses six maps $\F_2^3\to\F_2^2$ with distinct one-dimensional kernels. A nonzero input therefore makes at most one external position vanish, and vertex-bit cuts connect the clique interiors. This supplies eight codewords and completes the exact comparison.

\emph{Organization.} Section~2 constructs the nine words (Lemma~\ref{lem:words}) and proves that ten are impossible (Lemma~\ref{lem:bound}). Section~3 transfers this bound to $G$ (Proposition~\ref{prop:upper}). Sections~4 and~5 give the local repairs (Lemma~\ref{lem:repair}) and the lift (Theorem~\ref{thm:lift}). Section~6 gives the optimal linear code (Proposition~\ref{prop:linear}), and Section~7 proves the conditional order bound (Proposition~\ref{prop:order}).

\section{Nine words on a four-element alphabet}
Put $X=\F_3^2$. All arithmetic used to define the following partitions is in $\F_3$.
For $r\in\F_3$, the partition $P_r$ has the triple
\[
 \{(r,b):b\in\F_3\},
\]
labelled $3$, and the three pairs
\begin{equation}\label{eq:P}
 \{(r+1,c),(r+2,c+1)\},\qquad c\in\F_3,
\end{equation}
labelled $c$. The triple covers one row and the pairs cover the other two rows, each point once. For $t\in\F_3$, the partition $Q_t$ has triple $\{(a,t):a\in\F_3\}$, labelled $3$, and pairs
\begin{equation}\label{eq:Q}
 \{(c,t+1),(c-1,t+2)\},\qquad c\in\F_3,
\end{equation}
labelled $c$. These partition the remaining two columns.
For $p\in X$, let $w(p)$ record its six block labels in the order
\[
 P_0,P_1,P_2,Q_0,Q_1,Q_2.
\]
Thus every coordinate has symbol classes of sizes $3,2,2,2$.
\begin{lemma}\label{lem:words}
The nine words $w(p)$ are distinct, and every two agree in exactly one coordinate.
\end{lemma}
\begin{proof}
Agreement means that the two points belong to one block. Points with the same first coordinate $a$ share the triple of $P_a$. They share no other triple, and no pair in~\eqref{eq:P} or~\eqref{eq:Q} has equal first coordinates. Points with the same second coordinate share only the corresponding $Q$-triple, since every pair block has distinct second coordinates.

For points differing in both coordinates, interchange their order so they are $(a,b)$ and $(a+1,b')$. If $b'=b+1$, they form the pair labelled $b$ in $P_{a-1}$. If $b'=b-1$, they form the pair labelled $a+1$ in $Q_{b+1}$. These are the only possibilities in $\F_3$. A $P$-pair has difference $\pm(1,1)$, and a $Q$-pair has difference $\pm(1,-1)$, so these possibilities do not overlap. The $P$ index is fixed by the missing first-coordinate value; the $Q$ index is fixed by the missing second-coordinate value. There is therefore exactly one shared block in this case too. No pair of distinct points shares all six labels, proving distinctness.
\end{proof}
For reference, the complete auxiliary code is
\begin{center}
\begin{tabular}{c@{\qquad}rrrrrr}
\toprule
$p$ & $P_0$&$P_1$&$P_2$&$Q_0$&$Q_1$&$Q_2$\\
\midrule
$(0,0)$&3&2&0&3&1&0\\
$(0,1)$&3&0&1&0&3&1\\
$(0,2)$&3&1&2&1&0&3\\
$(1,0)$&0&3&2&3&2&1\\
$(1,1)$&1&3&0&1&3&2\\
$(1,2)$&2&3&1&2&1&3\\
$(2,0)$&2&0&3&3&0&2\\
$(2,1)$&0&1&3&2&3&0\\
$(2,2)$&1&2&3&0&2&3\\
\bottomrule
\end{tabular}
\end{center}

\begin{lemma}\label{lem:bound}
A four-symbol code of length six in which distinct words agree at most once has at most nine words.
\end{lemma}
\begin{proof}
If there were ten or more, select ten. At one coordinate let the four symbol multiplicities be $n_0,n_1,n_2,n_3$, summing to ten. The number of agreeing pairs there is $\sum_s\binom{n_s}{2}$. If $n_s\geq n_t+2$, moving one occurrence from $s$ to $t$ decreases this sum by $n_s-n_t-1>0$. A minimum consequently has multiplicities $3,3,2,2$ and value eight. The six coordinates contribute at least $48$ pair-coordinate agreements. There are only $\binom{10}{2}=45$ pairs, each allowed at most one agreement, a contradiction.
\end{proof}
This elementary agreement count and Lemma~\ref{lem:words} determine the auxiliary optimum exactly. The graph construction below uses more than this optimum: it also uses the fact that every symbol class has at least two points.

\section{The graph and its universal upper bound}
The graph $G$ has $3\cdot4+3=15$ vertices. Its internal edges number $3\binom42=18$, and~\eqref{eq:graph} contributes twelve more. All edges have distinct endpoints and no listed pairs repeat. Each clique vertex has three internal neighbors and one hub neighbor. The neighbors of $h_i$ are $a_i,b_i,c_{i-1},d_{i-1}$. This proves simplicity and regularity in Theorem~\ref{thm:main}.

For an edge set $A$, record each external pair as a binary pair:
\begin{align}
 \pi(A)_{2i}&=(\mathbf1_{h_i a_i\in A},\mathbf1_{h_i b_i\in A}),\label{eq:projection}\\
 \pi(A)_{2i+1}&=(\mathbf1_{h_{i+1}c_i\in A},\mathbf1_{h_{i+1}d_i\in A}).\notag
\end{align}
The six coordinates follow the cyclic order
\begin{equation}\label{eq:cycle}
 h_0,U_0,h_1,U_1,h_2,U_2,h_0.
\end{equation}
Here each $U_i$ becomes a single vertex when the clique is identified.
\begin{figure}[ht]
\centering
\begin{tikzpicture}[scale=.72,every node/.style={font=\small}]
\node[circle,draw,minimum size=8mm] (h0) at (0,2) {$h_0$};
\node[draw,rounded corners,minimum size=8mm] (u0) at (2,1) {$U_0$};
\node[circle,draw,minimum size=8mm] (h1) at (2,-1) {$h_1$};
\node[draw,rounded corners,minimum size=8mm] (u1) at (0,-2) {$U_1$};
\node[circle,draw,minimum size=8mm] (h2) at (-2,-1) {$h_2$};
\node[draw,rounded corners,minimum size=8mm] (u2) at (-2,1) {$U_2$};
\foreach \a/\b in {h0/u0,u0/h1,h1/u1,u1/h2,h2/u2,u2/h0}
 \draw[double,double distance=2pt] (\a)--(\b);
\end{tikzpicture}
\caption{The external quotient. Each box represents a complete graph on four vertices, not a single vertex of $G$. Each double link represents the two distinct external edges in~\eqref{eq:graph}.}
\label{fig:quotient}
\end{figure}

\begin{proposition}\label{prop:upper}
Every connectivity code in $G$ has at most nine members, and every linear one has at most eight.
\end{proposition}
\begin{proof}
Suppose $A\triangle B$ is connected and spanning. Identify each $U_i$ to one vertex, delete loops, and merge parallel edges. Connectivity is preserved by these operations. The resulting graph is a connected spanning subgraph of the six-cycle~\eqref{eq:cycle}. A position is occupied exactly when $\pi(A)$ and $\pi(B)$ differ there. At least five positions must be occupied, since a connected graph on six vertices has at least five edges.

Hence $\pi$ is injective on any connectivity code, and its images agree in at most one coordinate. The alphabet $\F_2^2$ has four elements, so Lemma~\ref{lem:bound} gives the upper bound nine. The cardinality of a binary vector subspace is a power of two; its size is therefore at most eight.
\end{proof}

\section{A four-vertex gadget and its repairs}
For a vertex subset $S$ of a graph $K$, write $\delta_K(S)$ for the cut consisting of edges with one endpoint in $S$. Edgewise parity gives
\begin{equation}\label{eq:cut}
 \delta_K(S)\triangle\delta_K(T)=\delta_K(S\triangle T).
\end{equation}
If $K$ is connected, its empty cut comes only from $\varnothing$ and the full vertex set. Thus two subsets have the same cut exactly when they are equal or complementary. The cut space of $K_4$ has eight members: the empty cut, four singleton cuts, and three cuts of type $2+2$. Every nonempty cut is a connected spanning complete bipartite graph.

These eight cuts can label eight of the desired nine edge sets. Toggling the same internal edge in each label preserves all differences between them. The remaining task is to make their differences with a distinguished empty edge set connected. For an empty internal cut, even all four external edges give two disjoint stars, one at each hub. The edge $ac$ joins these stars. Toggling it causes two other cuts to lose internal connectivity, but each can be repaired by a full external pair on one side. The next lemma records these three repairs.

\Needspace{17\baselineskip}
\begin{lemma}\label{lem:repair}
Let $K$ be the clique on $a,b,c,d$, and put $e=ac$. Add distinct possible hubs $L,R$, with any selected edges from $\{La,Lb\}$ and $\{Rc,Rd\}$. Include a hub as a vertex only if at least one of its edges is selected. Starting with the internal edge set $F\triangle\{e\}$ for a cut $F$ of $K$, the resulting local graph is connected in each of these situations:
\begin{enumerate}[label=(\roman*)]
\item $F\notin\{\varnothing,\delta_K(\{a\}),\delta_K(\{c\})\}$, with arbitrary external selections;
\item $F=\varnothing$, with all four external edges selected;
\item $F=\delta_K(\{a\})$, with both right edges selected;
\item $F=\delta_K(\{c\})$, with both left edges selected.
\end{enumerate}
\end{lemma}
\begin{proof}
For the five cuts in (i), the internal graph is connected. The singleton cuts at $b,d$ do not contain $ac$, so the operation adds an edge to a spanning star. Each $2+2$ cut is a $K_{2,2}$; adding $ac$ preserves connectivity if it was absent, while deleting it leaves a spanning path if it was present. Every included hub attaches to this connected internal graph.

In (ii), the internal graph is the single edge $ac$, and the external edges supply the spanning path $b,L,a,c,R,d$. In (iii), the internal edges are $ab,ad$, and the path $b,a,d,R,c$ connects the four clique vertices and $R$. Any included $L$ attaches at $a$ or $b$. In (iv), the internal edges are $bc,cd$, and $a,L,b,c,d$ is a spanning path through the clique and $L$. Any included $R$ attaches at $c$ or $d$. These paths establish each case.
\end{proof}
The lemma permits an internal difference to be disconnected when the external edges repair it. Requiring all nine codewords to have connected pairwise differences within a single clique would be impossible: restriction to the three edges incident with any vertex of $K_4$ is injective on such a family, bounding its size by $2^3=8$.

\section{Lifting the nonlinear code}
Fix $o=(0,0)\in X$. Coordinates are numbered $0,\ldots,5$ in the order used above. For each $i\in\{0,1,2\}$, select $p_i\ne o$ whose word disagrees with $w(o)$ at both coordinates $2i,2i+1$. Such a point exists: at each coordinate at most two other points share $o$'s symbol, so the two coordinates exclude at most four of the eight candidates.

Let $D_i^L,D_i^R$ be the symbol classes of $p_i$ at these two coordinates. Each has at least two points, neither contains $o$, and
\begin{equation}\label{eq:intersection}
 D_i^L\cap D_i^R=\{p_i\}.
\end{equation}
Indeed, any second point in the intersection would agree with $p_i$ twice. Choose $q_i\in D_i^R\setminus\{p_i\}$ and $r_i\in D_i^L\setminus\{p_i\}$. They are distinct from each other, from $p_i$, and from $o$.
The following choices can be read directly from the auxiliary-word table:
\begin{center}
\begin{tabular}{cclll}
\toprule
$i$ & Coordinates & $p_i$ & $q_i$ & $r_i$\\
\midrule
0 & $P_0,P_1$ & $(1,0)$ & $(1,1)$ & $(2,1)$\\
1 & $P_2,Q_0$ & $(0,1)$ & $(2,2)$ & $(1,2)$\\
2 & $Q_1,Q_2$ & $(0,1)$ & $(1,0)$ & $(1,1)$\\
\bottomrule
\end{tabular}
\end{center}
Different gadgets may use the same points; no cross-gadget distinctness is required.

For $j\in\{2i,2i+1\}$ choose a bijection $\gamma_j:\{0,1,2,3\}\to\F_2^2$ with
\[
 \gamma_j(w(o)_j)=00,\qquad \gamma_j(w(p_i)_j)=11.
\]
The two specified symbols are different, so this leaves exactly the two other binary pairs to assign. Set $\widetilde w(p)_j=\gamma_j(w(p)_j)$. Agreements are unchanged, $\widetilde w(o)$ is zero, and
\begin{equation}\label{eq:repairs}
 \widetilde w(p_i)_{2i}=\widetilde w(p_i)_{2i+1}=11,\quad
 \widetilde w(q_i)_{2i+1}=11,\quad \widetilde w(r_i)_{2i}=11.
\end{equation}
Each coordinate belongs to just one gadget pair, so the six bijections can be chosen independently.

Let $K_i=G[U_i]$ and let $\D_i$ be its eight-element cut space. Choose a bijection $F_i:X\setminus\{o\}\to\D_i$ such that
\begin{equation}\label{eq:exceptional}
 F_i(p_i)=\varnothing,\qquad
 F_i(q_i)=\delta_{K_i}(\{a_i\}),\qquad
 F_i(r_i)=\delta_{K_i}(\{c_i\}).
\end{equation}
The three prescribed points and cuts are distinct, so this extends by matching the remaining five points to the remaining five cuts. These choices are finite and explicit. For a completely fixed convention, send the remaining two symbols in increasing order to $01,10$, and send the five remaining points in lexicographic order to the remaining cuts in the lexicographic order of their three vertex bits on $b_i,c_i,d_i$, with the bit on $a_i$ fixed to zero.

Set $A_o=\varnothing$. For $p\ne o$ define
\begin{equation}\label{eq:lift}
 A_p\cap E(K_i)=F_i(p)\triangle\{a_ic_i\},\qquad
 \pi(A_p)=\widetilde w(p).
\end{equation}
Internal and external edges are disjoint, so these prescriptions define every edge of $A_p$.
\begin{example}
Consider the word indexed by $p=(1,0)$ in the first gadget. Its symbols at $P_0,P_1$ are $0,3$, while $o$ has symbols $3,2$. The specified relabellings therefore give $\widetilde w(p)_0=\widetilde w(p)_1=11$. Since $p=p_0$, its internal cut is empty, and its internal edge set after the toggle is just $a_0c_0$. This single edge, together with the four external edges, supplies the path
\[
 b_0,h_0,a_0,c_0,h_1,d_0.
\]
Thus the restriction to the clique is disconnected, but the local subgraph containing its two hubs is connected. This is the exceptional repair that allows the ninth codeword.
\end{example}
\begin{theorem}\label{thm:lift}
The nine sets $A_p$, for $p\in X$, form a connectivity code in $G$.
\end{theorem}
\begin{proof}
The external words are distinct, so all nine sets are distinct. First take $p,q\ne o$ with $p\ne q$. Inside $K_i$, the toggled edge cancels and the difference is $F_i(p)\triangle F_i(q)$. By~\eqref{eq:cut} it is a cut; by injectivity of $F_i$ it is nonempty. It is therefore connected and spanning inside every clique. The external words agree exactly once, so their difference occupies five cycle positions and connects the six quotient vertices along a path. Replacing each clique vertex of that path by its connected internal graph proves that $A_p\triangle A_q$ is connected and spans $G$.

It remains to compare a nonzero index $p$ with $o$. The external word $\widetilde w(p)$ agrees with the zero word exactly once. Precisely one external position is absent. For each $i$, let $T_i$ consist of all four clique vertices, the edges prescribed in~\eqref{eq:lift}, and those adjacent hubs incident with a present external edge.
If $p=p_i$, both external pairs are full by~\eqref{eq:repairs}, and Lemma~\ref{lem:repair}(ii) applies. If $p=q_i$, the right pair is full and part (iii) applies. If $p=r_i$, the left pair is full and part (iv) applies. For every other $p$, bijectivity in~\eqref{eq:exceptional} excludes the three exceptional cuts, so part (i) applies. Thus each $T_i$ is connected and contains its whole clique.

Let $k$ be the unique gadget incident with the absent cycle position. The two gadgets $i\ne k$ each have both external positions occupied. Their connected local graphs join $h_i$ to $h_{i+1}$; these two hub pairs form a path through all three hubs. Every gadget has at least one occupied external position, since only one is absent globally. Therefore every $T_i$ meets this connected hub component. All fifteen vertices lie in one component, proving that $A_p=A_p\triangle A_o$ is connected and spanning.
\end{proof}
Together with Proposition~\ref{prop:upper}, this proves $m(G)=9$.

\section{The optimal linear code}
\begin{proposition}\label{prop:linear}
The graph $G$ has a three-dimensional linear connectivity code. Consequently $\Clin(G)=8$.
\end{proposition}
\begin{proof}
For $u=(x,y,z)\in\F_2^3$, prescribe the external word
\begin{equation}\label{eq:linear}
 L(u)=((y,z),(x,z),(x,y),(x+y,z),(x+z,y),(y+z,x)).
\end{equation}
The six coordinate maps have kernels generated respectively by
\[
 (1,0,0),\ (0,1,0),\ (0,0,1),\ (1,1,0),\ (1,0,1),\ (0,1,1).
\]
These vectors are distinct. Thus any nonzero input makes at most one binary-pair coordinate zero. At least five external cycle positions are occupied.

Inside each clique assign the vertex bits $(0,x,y,z)$ to $(a_i,b_i,c_i,d_i)$ and select an edge when its two bits differ. For nonzero $u$ the bits are not constant, so the selected internal edges form a nonempty cut and are connected and spanning. With the external prescription~\eqref{eq:linear}, let the resulting edge set be $B_u$. Its internal graphs connect through a spanning path of occupied quotient positions, so $B_u$ is connected and spanning whenever $u\ne0$.

Every edge indicator is a linear function of $u$: internally it is the sum of its endpoint bits, and externally it is a coordinate of~\eqref{eq:linear}. Hence $B_u\triangle B_v=B_{u+v}$. No nonzero input maps to the empty set, because its image is connected and spans fifteen vertices. The map is therefore injective, and its image is a three-dimensional linear code with eight members. Proposition~\ref{prop:upper} gives the matching upper bound.
\end{proof}
This completes Theorem~\ref{thm:main}. The existence question is answered without assuming that fifteen is the smallest possible graph order for a separation.

\section{Order within the doubled-six-cycle framework}
The construction does have an order-minimality property under explicit hypotheses.
\begin{proposition}\label{prop:order}
Let $J$ be a simple graph partitioned into six nonempty parts $V_0,\ldots,V_5$, indexed cyclically. Suppose exactly two edges join each consecutive pair and no other edges join different parts. If $m(J)\geq9$, then $|V(J)|\geq15$. The graph $G$ attains this bound in this class.
\end{proposition}
\begin{proof}
Restriction to the edges incident with a vertex $v$ is injective on any connectivity code: a difference with zero restriction isolates $v$, whereas the graph has at least six vertices. A code with nine members therefore forces $9\leq2^{d_J(v)}$, and hence $d_J(v)\geq4$ for every vertex.

A part of size $t$ has exactly four outgoing edges. Simplicity bounds its internal edge count by $\binom t2$. Summing degrees over that part gives
\[
 4t\leq\sum_{v\in V_i}d_J(v)=2|E(J[V_i])|+4\leq t(t-1)+4.
\]
Thus $(t-1)(t-4)\geq0$, so a nonempty part has size one or at least four. Adjacent parts cannot both be singletons, since two distinct edges cannot join the same two vertices in a simple graph. At most three parts are therefore singletons. If their number is $s\leq3$, then
\[
 |V(J)|\geq s+4(6-s)=24-3s\geq15.
\]
For $G$, the alternating parts $\{h_0\},U_0,\{h_1\},U_1,\{h_2\},U_2$ meet all these hypotheses and have total size fifteen. Theorem~\ref{thm:lift} gives the required nine codewords.
\end{proof}

\section{Concluding remarks}
The strict inequality is an existence result of the type asked in Question~\ref{q:source}, with exact optima on a specified graph. It does not establish a growing nonlinear-to-linear ratio or characterize all graphs admitting a separation. The conditional order bound also does not exclude smaller examples outside the doubled-six-cycle framework, or examples whose optimal code has another size. The local repair shows that connected differences need not be assembled from independently connected internal pieces; their external incidence can supply the missing connections.

\begin{thebibliography}{99}
\bibitem{AGKMS} N. Alon, A. Gujgiczer, J. K\"orner, A. Milojevi\'c, and G. Simonyi, \emph{Structured codes of graphs}, SIAM Journal on Discrete Mathematics \textbf{37} (2023), no.~1, 379--403. \url{https://doi.org/10.1137/22M1487989}.
\bibitem{Alon} N. Alon, \emph{Connectivity graph-codes}, Random Structures \& Algorithms \textbf{65} (2024), no.~3, 451--459. \url{https://doi.org/10.1002/rsa.21222}. Revised author manuscript: \url{https://web.math.princeton.edu/~nalon/PDFS/GCII3.pdf}.
\bibitem{GraphCodes} N. Alon, \emph{Graph-codes}, European Journal of Combinatorics \textbf{116} (2024), article 103880. \url{https://doi.org/10.1016/j.ejc.2023.103880}. \url{https://arxiv.org/abs/2301.13305}.
\bibitem{Survey} N. Alon, \emph{Graph-codes: questions, results and methods}, Japanese Journal of Mathematics (2026), published online 12 July 2026. \url{https://doi.org/10.1007/s11537-026-2536-1}.
\bibitem{BGMW} B. Bai, Y. Gao, J. Ma, and Y. Wu, \emph{Phase transitions of structured codes of graphs}, SIAM Journal on Discrete Mathematics \textbf{38} (2024), no.~2, 1902--1914. \url{https://doi.org/10.1137/23M1614572}. Preprint: \url{https://arxiv.org/abs/2307.08266v1}.
\bibitem{BergerZhao} A. Berger and Y. Zhao, \emph{$K_4$-intersecting families of graphs}, Journal of Combinatorial Theory, Series~B \textbf{163} (2023), 112--132. \url{https://doi.org/10.1016/j.jctb.2023.07.005}.
\bibitem{EFF} D. Ellis, Y. Filmus, and E. Friedgut, \emph{Triangle-intersecting families of graphs}, Journal of the European Mathematical Society \textbf{14} (2012), no.~3, 841--885. \url{https://doi.org/10.4171/JEMS/320}.
\bibitem{GJS} L. Gishboliner, Z. Jin, and B. Sudakov, \emph{Difference-isomorphic graph families}, Journal of Combinatorial Theory, Series~B \textbf{180} (2026), 25--61. \url{https://doi.org/10.1016/j.jctb.2026.06.001}.
\bibitem{HKCSS} A. R. Hammons, P. V. Kumar, A. R. Calderbank, N. J. A. Sloane, and P. Sol\'e, \emph{The $\mathbb Z_4$-linearity of Kerdock, Preparata, Goethals, and related codes}, IEEE Transactions on Information Theory \textbf{40} (1994), no.~2, 301--319. \url{https://doi.org/10.1109/18.312154}.
\bibitem{NR} A. W. Nordstrom and J. P. Robinson, \emph{An optimum nonlinear code}, Information and Control \textbf{11} (1967), no.~5--6, 613--616. \url{https://doi.org/10.1016/S0019-9958(67)90835-2}.
\bibitem{Plotkin} M. Plotkin, \emph{Binary codes with specified minimum distance}, IRE Transactions on Information Theory \textbf{6} (1960), no.~4, 445--450. \url{https://doi.org/10.1109/TIT.1960.1057584}.
\bibitem{Tian} C. Tian, \emph{Maximal connectivity graph-codes exist in every degree at least four: $f(d)=2^d$ for all $d\geq4$, answering a question of Alon}, arXiv:2609.02953v1, 2 September 2026, Section~6(c). Listed on arXiv as \emph{Alon's Question on Connectivity Graph-Codes: $f(d)=2^d$ for Every $d\geq4$}. \url{https://arxiv.org/abs/2609.02953v1}.
\bibitem{Versteegen} L. Versteegen, \emph{Upper bounds for linear graph codes}, Random Structures \& Algorithms \textbf{66} (2025), no.~1, article e21263. \url{https://doi.org/10.1002/rsa.21263}. \url{https://arxiv.org/abs/2310.19891}.
\end{thebibliography}
\end{document}