\documentstyle[a4,12pt]{article}
\include{aebdefs}
\title{The vertex connectivity of a $\{0,2\}$-graph equals its degree}
\author{A.E. Brouwer\\
{\small Department of Mathematics}\\
{\small Eindhoven University of Technology}\\
{\small P.O. Box 513, 5600 MB \ Eindhoven, The Netherlands}
\bigskip \\
H.M. Mulder\\
{\small Econometrisch Instituut}\\
{\small Erasmus Universiteit Rotterdam}\\
{\small Burgemeester Oudlaan 50, 3062 PA \ Rotterdam, The Netherlands}}
\date{26 September 1996}
\begin{document}
\maketitle


\begin{abstract}
The first author observed that nice graphs are regular and have
vertex connectivity equal to the degree.
The second author observed that $\{0,2\}$-graphs are nice.
This note follows immediately.
\end{abstract}


A $\{0,2\}$-graph is a connected graph such that any two distinct vertices
have either 0 or 2 common neighbours. These graphs were introduced in
\cite{M79} as a generalization of hypercubes.
Examples are $K_m$ ($m = 1,2,4$), the icosahedron,
the Shrikhande graph on 16 vertices, the Klein map on 24 vertices,
the incidence graphs of biplanes and Cartesian products of $\{0,2\}$-graphs.
Note that $\{0,2\}$-graphs can have a more messy structure than these
examples suggest.

It is easy to see that each
$\{0,2\}$-graph is regular, and that a $\{0,2\}$-graph of valency $d$
has at most $2^d$ vertices. The hypercubes are precisely the
$\{0,2\}$-graphs attaining this maximum for the number of vertices,
see \cite{M79,M80}, cf. \cite{BCN}.
In this note we prove the following result.

\begin{Theorem}
Let $G$ be a noncomplete $\{0,2\}$-graph of finite degree $d$.
Then the vertex connectivity $\kappa (G)$ equals $d$, and the only
cut sets of size $d$ are the vertex neighbourhoods, except when
$G = K_2 \times K_4$, in which case there is a cut set of size 4
that splits $G$ into two edges.
\end{Theorem}

\medskip
\Proof
Trivially, $\kappa (G) \le d$.
Let $S$ be a cut set of minimum size in $G$ that is not
a vertex neighbourhood.
Put $s := |S|$, and assume that $s \le d$.
Let $G \setminus S = A + B$
be a separation of $G \setminus S$ into two nonempty pieces.

Let us write $N(p)$ for the set of neighbours of the vertex $p$ in
$G$, and, more generally, let $N(p,q,...)$ denote the set of
common neighbours of the vertices $p,q,...$.
For any vertex $p$ of $G$, let $S_p := N(p) \cap S$.
For $x \in S$, let $A_x := N(x) \cap A$ and $B_x := N(x) \cap B$.
Let $a_x := |A_x|$ and $b_x := |B_x|$ and $s_x := |S_x|$ so that
$a_x + b_x + s_x = d$ for $x \in S$.
Note that $a_x > 0$ and $b_x > 0$ since $S$ is minimal.

For $x \in S$, let $C_x$ consist of the common neighbours distinct
from $x$ of a vertex in $A_x$ and one in $B_x$.
Then $|C_x| = a_x b_x$ and $C_x \subseteq S$.
Note that $1 + a_x b_x \le s \le d$.

\medskip
Step 1.
{\it No vertex of $S_x$ is adjacent to a vertex of $C_x$.}

Indeed, if $p \in S_x$ is adjacent to $q \in C_x$, then $x$ and $q$ have
more than two common neighbours.

\medskip
Step 2.
{\it For all $x \in S$ we have $s_x > 0$.}

Indeed, if $s_x = 0$, then $s \ge 1 + a_x b_x > d$, unless min$(a_x,b_x) = 1$.
But if $A_x = \{a\}$, then $S = N(a)$ is a vertex neighbourhood.

\medskip
Step 3.
{\it For all $x \in S$ we have $s_x > 1$, unless we have the exceptional
example.}

Indeed, suppose $S_x = \{y\}$.
Then $y \not\in C_x$, since $N(x)$ is a disjoint union of cycles
(of length not equal to 4), and $y$ cannot disconnect the cycle
on $y$ in $N(x)$.
Now $s \ge 2 + a_x b_x > d$, unless ${\rm min}(a_x,b_x) = 1$
(and in that case $S = C_x \cup \{ x,y\}$).
Assume $a_x = 1$, so that $b_x = d-2$, and put $A_x = \{a\}$.
If $a' \in A \setminus \{a\}$ is adjacent to $p \in S \setminus \{x\}$,
then choose $b \in B_p$, and define $q$ by $N(a',b) = \{p,q\}$.
Now $N(p,q) = \{a',b\}$ so not both $p$ and $q$ are in $S_a$,
and one of them is $y$. Now necessarily $N(x,a') = \{y,a\}$,
so that $a'$ is uniquely determined by $\{ a' \} = N(y,a) \setminus \{x\}$.
Consequently, $|A| = 2$.
By Step 1, $s_y = 1$, so that $N(a') = \{a\} \cup S \setminus \{x\}$.
Now $a$ and $a'$ have $d-2$ common neighbours, so $d=4$ and we find
the exceptional example.

So, we may assume that $G$ is not $K_2 \times K_4$,
so that $s_x \ge 2$ for all $x \in S$.

\medskip
Step 4.
{\it For all $x \in S$ we have $s_x < d-3$.}

Indeed, suppose $s_x \ge d-3$. If $c \in C_x$, then, since $d-1-s_x \le 2$
and $s_c \ge 2$ and there is no edge between $C_x$ and $S_x$, we have
$c \in S_x$.
Since $x \in S_c$ and there is no edge between $C_c$ and $S_c$, we have
$|C_c| \le 3$. Thus, ${\rm min}(a_x,b_x) = {\rm min}(a_c,b_c) = 1$.
But if $a_x = a_c = 1$ or $b_x = b_c = 1$, then we can replace $\{x,c\}$
by $A_x$ or $B_x$, respectively, and find a smaller cut set.
So, without loss of generality, we have $a_x = 1$, $b_x = 2$,
$s_x = d-3$, $b_c = 1$.
Put $A_x = \{a\}$, $B_x = \{b,b'\}$.
Then $C_x = \{c,c'\}$, with $N(a,b) = \{x,c\}$ and $N(a,b') = \{x,c'\}$.
Also $b_{c'} = 1$.
Let $N(b,c) = \{x,e\}$ and $N(b',c') = \{x,e'\}$.
Then $e,e' \in S \setminus S_x$ (indeed, $e \in S$ since $b_c = 1$,
and $e \not\in S_x$, otherwise $\{a,b,e\} \subseteq N(x,c)$)
and $e \ne e'$ (otherwise $\{a,x,e\} \subseteq N(c,c')$).
We have $e' \in N(e)$ since $s_e \ge 2$.
But then $e' \not\in C_c$, so $C_c = S_c = \{x,e\}$
(since both $C_c$ and $S_c$ contain $x$, and neither contains $e'$,
and there are no edges between $C_c$ and $S_c$)
and $C_{c'} = S_{c'} = \{x,e'\}$ and $a_c = a_c' = 2$.
Now $d = a_c + b_c + s_c = 5$ and $S$ is a pentagon ${\bf Z}_5$
with $i$ adjacent to $i+1$, and the points outside $S$ are adjacent
to triples $i-1,i,i+1$ inside, and alternate between $A$ and $B$.
But 5 is odd, contradiction.

\medskip
Step 5.
{\it For no $x \in S$ do we have ${\rm min}(a_x,b_x) = 1$ and $s_x = 2$.}

Indeed, if $A_x = \{x'\}$ and $s_x = 2$, then look at
$S' = \{x'\} \cup S \setminus \{x\}$.
This is a cut set, and not a vertex neighbourhood, since
$|S' \cap N(x)| = 3$.
But $|N(x') \cap S'| \ge b_x = d-3$, contrary to Step 4.

\medskip
Final contradiction.
Call a pair $\{x,y\}$ of vertices in $S$ {\em red} if $y \in C_x$.
Call a pair $\{x,y\}$ of vertices in $S$ {\em green} if $x,y \in S_z$
for some $z \in S$. Clearly, a pair cannot be both red and green.
There are ${1 \over 2} \sum_{x \in S} a_x b_x$ red pairs,
and at least ${1 \over 2} \sum_{x \in S} {s_x \choose 2}$ green pairs.
Consequently,
$$\sum_{x \in S} a_x b_x + \sum_{x \in S} {s_x \choose 2} \le s(s-1) ,$$
that is (with $s = d - \delta$, $\delta \ge 0$)
$$\sum_{x \in S} ((a_x - 1)(b_x - 1) + {1 \over 2} s_x(s_x - 3) + \delta) \le 0 .$$
But by Steps 3 and 5 all terms are nonnegative.
So, all terms must be zero, and we find $\delta = 0$ and for each $x$
either $a_x = b_x = s_x = 2$ or ${\rm min}(a_x,b_x) = 1$ and $s_x = 3$.
Moreover, since we have equality in our inequalities,
each green pair is seen twice, so that any two vertices of $S$
have 0 or 2 common neighbours in $S$, and each component of $S$ is regular,
but if $s_x = 2$ then $d = 6$ while the component of $x$ has size 4,
impossible. So, $s_x = 3$ for all $x$.
Again considering a replacement of $x$ by $x'$ as in the proof of Step 5,
we see that $d = 7$ and $S$ is a cubic graph on 7 vertices,
so has 21/2 edges, contradiction.

\begin{thebibliography}{}

\bibitem[1]{BCN} A.E. Brouwer, A.M. Cohen \& A. Neumaier,
{\it Distance-regular graphs\/},
Springer Verlag, Berlin, 1989.

\bibitem[2]{M79} H.M. Mulder,
{\it $(0,\lambda)$-graphs and $n$-cubes\/},
Discrete Math. {\bf 28} (1979) 179-188.

\bibitem[3]{M80} H.M. Mulder,
{\it The interval function of a graph\/},
Mathematical Centre Tracts 132, Mathematisch Centrum, Amsterdam, 1980.

\end{thebibliography}

\end{document}
