In the following few pages we give the current version of Section 3.14 and the first part of 3.15 (pp. 113-120). For the position of distance-regular graphs in the metric hierarchy, see .SC Koolen .[[ Koolen Master's thesis metric properties 1990 .]], .SC Koolen & Shpectorov .[[ Koolen Shpectorov 1994 positive eigenvalue .]], .SC Shpectorov .[[ Shpectorov isometric halved cube .]]. .bp .nr H1 3 .nr H2 13 .Nh "Root graphs" A .I root representation .R .Xx "root representation" of a graph is an integral affine (2,4)-representation, i.e., a representation such that the squared distances $[ gam , del ] = ( gam bar - del bar , gam bar - del bar )$ of the images of all $gam , del mo GAM$ are even integers and satisfy .EQ C [ gam , del ] = 2i ~ if ~ d ( gam , del ) = i <= 2. .EN A connected graph having a root representation is called a .I root graph, .R .Xx "root graph" and a .I strict root graph .R .Xx "strict root graph" if the representation is strict, i.e., .EQ C [ gam , del ] = 2i <= 4 iff d ( gam , del ) = i <= 2. .EN The name reflects the fact that the lattice $Ll ( GAM )$ of a root representation of $GAM$, defined in Section 3.9, is a root lattice: .NH 3 .R $Pr$. .I Let $GAM$ be a root graph. Then $Ll ( GAM )$ is a root lattice. Moreover, if $GAM$ is locally connected, then $Ll ( GAM )$ is irreducible. .Bop Since $GAM$ is connected, $Ll ( GAM )$ is generated by the norm 2 vectors $gam bar - del bar$ ($gam , del mo GAM$, $gam adj del$), and is therefore a root lattice. Now suppose that $Ll ( GAM )$ is the direct sum of two lattices $Ll sub 1$ and $Ll sub 2$. If we call an edge $gam del$ of \fItype\fP $i$ if the norm 2 vector $gam bar - del bar$ is in $Ll sub i$ then each edge is either of type 1 or of type 2. If $alpha beta gam$ is a triangle, then $( alpha bar - beta bar , alpha bar - gam bar ) = 1$ so that edges in the same triangle have the same type. If $GAM$ is locally connected, then this implies that all edges have the same type, whence $Ll ( GAM ) = Ll sub 1$ or $Ll ( GAM ) = Ll sub 2$, showing that $Ll ( GAM )$ is irreducible. .Eop .LP Using the classification of root lattices we shall give a complete characterization of amply regular root graphs with $mu > 1$ in the next section. This leads in the next chapter to an important classification theorem for distance-regular graphs (Theorem $DrgRep$.11). $Re$. Related questions are considered by .SC Terwilliger .[[ Terwilliger root system graphs rsg .]], who considers structure theorems for (not necessarily regular) graphs having a spherical representation such that $[ gam , del ]$ is an even integer for all $gam , del mo GAM$ and $[ gam , del ] = 2$ if and only if $d ( gam , del ) = 1$. Root graphs generalize graphs with smallest eigenvalue $X>= -2$: .NH 3 .R $Th$. .IP (i) .I Every graph with smallest eigenvalue $X>= -2$ is a root graph. .IP (ii) .I A regular root graph of diameter $X<= 2$ has smallest eigenvalue $X>= -2$. .Bop (i) A graph with smallest eigenvalue $X>= -2$ has a spherical $(2,1,0)$-representation which is a root representation. .br (ii) By Proposition 3.5.6\|(ii), a regular root graph $GAM$ of diameter $X<= 2$ has a spherical $(p,p-1,p-2)$-representation for some $p > 0$; thus by Proposition 3.5.3\|(iii), $GAM$ has smallest eigenvalue $X>= -2$. .Eop The graphs $K sub 1,n$ are root graphs of diameter 2 with smallest eigenvalue $- sqrt n$, so regularity is required in part (ii) above. .Nb "Examples" The representation of $E sub 7 ( 1 )$ defined in \(sc3.11 is a root representation, so that any induced subgraph of $E sub 7 ( 1 )$ is a root graph. (However, $E sub 8 ( 1 )$, as given in \(sc3.11, contains vertices with squared distance 6 having a common neighbour, and hence defines no root representation). Further examples of root graphs are the \fIcode graphs\fP $GAM ( C )$, .Xx "code graph" defined by the words of a binary code $C$ of length $n$, words being adjacent if they differ in two entries (i.e., if their Hamming distance is 2); they have a natural representation by (0,1)-vectors in $Rr sup n$. We mention in particular the following amply regular code graphs. .LP .IP (i) The .I half-cube .R .Xx "half-cube" $D sub n,n (1)$ is the code graph of the binary code consisting of all even weight words of length $n$. $D sub n,n (1)$ has $2 sup {n-1}$ vertices, valency $Binom(n,2)$ and $mu = 6$. The graph $D sub 5,5 (1)$ is isomorphic to the Clebsch graph described in Section 3.11. .Xx "Clebsch graph" .IP (ii) The .I Johnson graph .R .Xx "Johnson graph" $J ( n , d )$ is the code graph of the binary code consisting of all words of length $n$ and weight $d$. $J (n,d)$ has $Binom(n,d)$ vertices, valency $d ( n - d )$ and $mu = 4$. In particular $(d = 1)$, $n$-cliques are code graphs. .IP (iii) The .I icosahedron .R .Xx "icosahedron" with 12 vertices, valency $5$ and $mu = 2$ can be viewed as the code graph of the binary code consisting of the words 000000, 110000, 001111, 111111, and those obtained by a cyclic permutation of the first five entries. .IP (iv) The .I Shrikhande graph .R .Xx "Shrikhande graph" with 16 vertices, valency 6 and $mu = 2$ can be viewed as the code graph of the binary code consisting of the words 000000, 110000, 010111, 011011 and those obtained by a cyclic permutation of the six entries (cf. Example 3.11\|(vi)). .IP (v) The .I Petersen graph .R .Xx "Petersen graph" with 10 vertices, valency 3 and $mu = 1$ can be viewed as the code graph of the binary code consisting of the words 000000, 100100, 001111 and those obtained by a cyclic permutation of the six entries (cf. Example 3.11\|(v)). .IP (vi) The .I dodecahedron .R .Xx "dodecahedron" with 20 vertices, valency 3 and $mu = 1$ can be viewed as the code graph of the binary code consisting of the words 11000\|00000, 11000\|11000 and their complements and those obtained by simultaneous cyclic permutation of the first five and the last five entries. .IP (vii) The $g$-\fIgon\fP with $g$ vertices, valency 2 and $mu = 1$ (when $g > 4$) is the code graph of the binary code consisting of the cyclic shifts of $1 sup 2 0 sup g-2$. (An isometric embedding in $D sub g,g (1)$ is given by the cyclic shifts of $1 sup a 0 sup g-a$ for $a = [g/2]$.) .IP (viii) The direct product $GAM$ of root graphs $GAM sup 1 , ... , GAM sup s$ is a root graph: simply represent $( gam sub 1 , ... , gam sub s )$ by the concatenation of the images of the $gam sub i$. (Now clearly $Ll ( GAM )$ is the direct sum of $Ll ( GAM sup 1 ) , ... , Ll ( GAM sup s )$.) Similarly, the direct product of code graphs is a code graph. In particular, the .I Hamming graphs .R .Xx "Hamming graph" (direct products of cliques) and .I Doob graphs .R .Xx "Doob graph" (the direct product of 4-cliques and Shrikhande graphs, cf. \(sc$ClassGr$.2B) are code graphs. .IP (ix) Of course, any induced subgraph of a code graph is again a code graph. In particular, as subgraphs of $n$-cubes, the doubled Odd graphs are code graphs. .LP We first prove some easy results about the local structure of root graphs. .NH 3 .R $Le$. .I Let $GAM$ be a root graph and $alpha , beta , gam mo GAM$. For the associated root representation we have .EQ I \fR(6)\fP 10n ( alpha bar - gam bar , beta bar - gam bar ) = mark 2 - d ( alpha , beta ) >= 0 ~~ if ~ alpha , beta mo GAM ( gam ) .EN .EQ I \fR(7)\fP = lineup 3 - d ( alpha , beta ) >= 0 ~~ if ~ alpha mo GAM ( gam ) ,~ beta mo GAM sub 2 ( gam ) , .EN .EQ I \fR(8)\fP = lineup 4 - d ( alpha , beta ) >= 0 ~~ if ~ alpha , beta mo GAM sub 2 ( gam ) , .EN provided that $d( alpha , beta ) <= 2$. In particular, if $gam bar = 0$, then points in $GAM ( gam )$ are represented by norm $2$ vectors, and points in $GAM sub 2 ( gam )$ are represented by norm $4$ vectors. .Bop By Lemma 3.5.1 we have .KS .EQ I "" 10n ( alpha bar - gam bar , beta bar - gam bar ) = mark 1o2 ( [ alpha , gam ] + [ beta , gam ] - [ alpha , beta ] - [ gam , gam ] ) .EN .EQ I = lineup d ( alpha , gam ) + d ( beta , gam ) - d( alpha , beta ) , .EN .KE which implies (6), (7) and (8). By putting $alpha = beta$ we obtain the second statement. .Eop .NH 3 .R $Pr$. .I Let $GAM$ be a root graph and $gam mo GAM$. Then: .IP (i) .I The local subgraph $GAM ( gam )$ has smallest eigenvalue $X>= -2$. .IP (ii) .I Two nonadjacent points $alpha , beta mo GAM ( gam )$ have at most one common neighbour in $GAM sub 2 ( gam )$, and such a neighbour is represented by $alpha bar + beta bar - gam bar$. .IP (iii) .I For $alpha , beta mo GAM$ at distance two, the graph $GAM ( alpha ) ca GAM ( beta )$ is complete multipartite with classes of size $1$ or $2$. .Bop (i) By Proposition 3.5.6\|(i), $GAM ( gam )$ has a (2,1,0)-representation. Thus, if $A$ denotes the adjacency matrix of $GAM ( gam )$, then the Gram matrix $G = 2I + A$ of the image of $GAM ( gam )$ is positive semidefinite. This implies (i). .br (ii) Now let $alpha , beta mo GAM ( gam )$ be nonadjacent. If $del mo GAM sub 2 ( gam )$ is a common neighbour of $alpha$ and $beta$ then Lemma 3.5.1 implies .EQ C ( del bar - alpha bar , beta bar - gam bar ) = 1o2 ([ del , gam ] + [ alpha , beta ] - [ del , beta ] - [ alpha , gam ]) = 1o2 (4 + 4 - 2 - 2) = 2. .EN Thus the norm of $( del bar - alpha bar ) - ( beta bar - gam bar )$ is $[ del , alpha ] - 2( del bar - alpha bar , beta bar - gam bar ) + [ beta , gam ] = 2 - 4 + 2 = 0$. Therefore $( del bar - alpha bar ) - ( beta bar - gam bar ) = 0$, so $del bar = alpha bar + beta bar - gam bar$, and, by Lemma 3.5.5, $del$ is unique. This implies (ii). .br (iii) Finally, let $d( alpha , beta ) = 2$. If $GAM ( alpha ) ca GAM ( beta )$ is not as claimed in (iii), then it contains three distinct points $gam , del , del prime$ such that $del , del prime nm GAM ( gam )$. But this contradicts part (ii). .Eop .NH 3 .R $Co$. .I Let $GAM$ be a root graph, $gam mo GAM$ and $Q$ a quadrangle in $GAM ( gam )$. Then if $del mo GAM ( gam ) minus Q$ is adjacent to some but not all vertices of $Q$, the set $del sup perp ca Q$ is an edge. .Bop $Q cu "{" del "}"$ is a connected graph on 5 vertices with smallest eigenvalue less than $-2$, unless $del sup perp ca Q$ is an edge. .Eop .NH 3 .R $Co$. .I Let $GAM$ be a root graph with $mu ( GAM ) = mu$. Then any two nonadjacent vertices $alpha , beta mo GAM ( gam )$ have either $mu - 1$ or $mu - 2$ common neighbours in $GAM ( gam )$. .Bop Among the $mu$ common neighbours of $alpha$ and $beta$, one is $gam$, and at most one is in $GAM sub 2 ( gam )$. The remaining neighbours must be in $GAM ( gam )$. .Eop .NH 3 .R $Le$. .I Let $GAM$ be a root graph with $Ll ( GAM ) ib Zz sup n+1$ and $gam$, $del$ vertices at distance two with $del bar - gam bar = 2e sub 0$, where $e sub 0 = (1,0, ... ,0)$. Then no vertex of $GAM ( gam ) ca GAM ( del )$ is adjacent to a vertex of $GAM ( gam ) minus GAM ( del )$. .Bop Without loss of generality we may assume that $gam bar = 0$ and $del bar = 2 e sub 0$. Lemma 3.14.3 shows that common neighbours of $gam$ and $del$ are represented by suitable vectors $e sub 0 +- e sub l$, and, by permuting the $e sub i$ and changing their signs if necessary, we may assume that $M := GAM ( gam ) ca GAM ( del )$ is represented by the $mu = 2 s + t$ vectors .EQ C e sub 0 +- e sub l ~~( l = 1 , ... , s ) , ~~~ e sub 0 + e sub l ~~( l = s + 1 , ... , s + t ). .EN Let $alpha mo M$ so that (for some $i$) $alpha bar = e sub 0 +- e sub i$, and suppose that $gam$ has a neighbour $beta nm M$ adjacent with $alpha$. Then $d ( beta , del ) = 2$; but either $beta bar = e sub 0 +- e sub j$, $( beta bar , del bar ) = 2$, or $beta bar = +- e sub i +- e sub j$ $( 0 != j != i != 0 )$, $( beta bar , del bar ) = 0$, both contradicting Lemma 3.14.3. Hence no point of $GAM ( gam ) minus GAM ( del )$ is adjacent to a point of $M$. .Eop .NH 3 .R $Pr$. .I Let $GAM$ be a root graph with $Ll ( GAM ) ib Zz sup n+1$ for some $n$, and \fR(*)\fP for no $gam , del mo GAM$ at mutual distance two do we have $del bar - gam bar = +- 2 e sub i$ for some $i$, $0 <= i <= n$. Then $GAM$ has a root representation in $"{"0,1"}" sup n+1$ sending an arbitrary $gam mo GAM$ to $0$. .Bop Given a root representation $rho : gam goesto gam bar = sum gam sub i e sub i$ satisfying (*), and a vector $u mo Zz sup n+1$, we find new root representations $rho - u : gam goesto gam bar - u$ and $vb rho vb : gam goesto sum vb gam sub i vb e sub i$ both satisfying (*). (Indeed, if $"{" del sub i - gam sub i mo "{" -1,0,1 "}"$ then $( del sub i - gam sub i ) sup 2 = ( vb del sub i vb - vb gam sub i vb ) sup 2$; in particular this holds for $d( gam , del ) <= 2$.) Let $rho$ be a root representation satisfying (*) in $"{"0,1,...,m"}" sup n+1$, where $m$ is chosen minimal. Then $m <= 1$, otherwise $vb rho - bold 1 vb$ would be a representation in $"{"0,1,...,m-1"}"$. Now $vb rho - rho ( gam ) vb$ is the required representation. .Eop .NH 3 .R $Le$. .I Let $GAM$ be a root graph with $Ll ( GAM ) ib Zz sup n+1$ and $mu ( alpha , beta ) >= 2$ for any two vertices $alpha , beta mo GAM$ at distance two. Suppose $d( gam , del ) <= 4$. \fR(i)\fP If $gam bar = del bar$, then $gam = del$. \fR(ii)\fP If $[ gam , del ] = 2$ then $gam adj del$. .Bop If $d( gam , del ) <= 2$, this is clear. We first prove part (ii). Assume $[ gam , del ] = 2$. If $d( gam , del ) = 3$, then choose $eps mo GAM ( gam ) ca GAM sub 2 ( del )$ and shift the representation such that $eps bar = 0$. We may assume that $gam bar = e sub i + e sub j$ and $del bar - gam bar = e sub k + e sub l$, with distinct $i,j,k,l$. The common neighbours of $del$ and $eps$ are represented by certain $e sub a + e sub b$ with $"{"a,b"}" ib "{"i,j,k,l"}"$, and since there are at least two of those, it follows that $gam$ has distance at most one to (at least) one of them, so that $d( gam , del ) <= 2$, contradiction. If $d( gam , del ) = 4$, then choose $eps mo GAM sub 2 ( gam ) ca GAM sub 2 ( del )$ and shift the representation such that $eps bar = 0$. We may assume that $gam bar = e sub i + e sub j + e sub k + e sub l$ and $del bar = e sub i + e sub j + e sub k + e sub m$. By the foregoing, no common neighbour of $gam$ and $eps$ is represented by $e sub a + e sub b$ with $"{"a,b"}" ib "{"i,j,k"}"$, so the (at least two) vertices in $gam sup perp ca eps sup perp$ are represented by $e sub a + e sub l$ for certain $a mo "{"i,j,k"}"$, and similarly those in $del sup perp ca eps sup perp$ by $e sub a + e sub m$ for certain $a mo "{"i,j,k"}"$. But then some vertex in $gam sup perp ca eps sup perp$ is adjacent to some vertex in $del sup perp ca eps sup perp$, so that $d( gam , del ) <= 3$, contradiction. This proves part (ii). But if $gam bar = del bar$, $gam , del mo GAM sub 2 ( eps )$, then by the above $gam sup perp ca eps sup perp = del sup perp ca eps sup perp$ and hence $d( gam , del ) <= 2$, contradiction. This proves part (i). .Eop .NH 3 .R $Pr$. .I Let $GAM$ be a root graph with $Ll ( GAM ) ib Zz sup n+1$ and noncomplete $mu$-graphs. Then for any $gam mo GAM$ the root representation is uniquely determined by its restriction to $gam sup perp$. If moreover $mu ( GAM ) = mu$ is constant, then $GAM$ itself is uniquely determined by the representation of $gam sup perp$. .Bop The first claim follows immediately from 3.14.4\|(ii). If $mu$ is constant, then the representation of $gam sup perp$ determines the structure and representation of $GAM sub 2 ( gam )$: for any two nonadjacent vertices $alpha , beta mo GAM ( gam )$ that have only $mu - 2$ common neighbours in $GAM ( gam )$, we find a vertex $del$ represented by $alpha bar + beta bar - gam bar$. But the restriction of the representation to $GAM sub { X<= 2 } ( gam )$ is injective, and determines the structure of this subgraph, by Lemma 3.14.9 above. Now vary the vertex $gam$. .Eop .Nh "Classification of amply regular root graphs" Let us first define one more family of graphs, and then show that all amply regular root graphs with $mu > 1$ are known. .LP Let $B(n,s)$ be the subgraph of the halved $(n+2)$-cube spanned by the $2 Binom(n,s-1) + 2 Binom(n,s)$ vectors of length $n+2$ and either weight $s+2$ starting $11 ...$ or weight $s$ starting $10 ...$ or $01 ...$ or $00 ...$. Then $B(n,s)$ is a root graph (indeed, a code graph) with $mu = 4$. It is regular if and only if $n = 2s-1$, and we put $B(s) := B(2s-1,s)$. Now $B(s)$ is regular of valency $s sup 2 + s + 1$, has diameter $s$, and satisfies $c sub i = i sup 2$ ($1 <= i <= s$). In particular, $B(1) isom K sub 4$, and $B(2)$ is one of the subgraphs of the Clebsch graph mentioned in 3.11\|(iii). For $s >= 2$, $Aut B(s)$ is transitive of rank $3s$. For more details, see .SC Brouwer & Koolen .[[ Brouwer Koolen infinite series .]]. .NH 3 .R $Th$. .I Let $GAM$ be a non-complete regular root graph with $mu ( GAM ) = mu > 2$. Then $GAM$ is locally connected and one of the following holds. .IP (i) .I $GAM isom K sub { n times 2 }$, where $mu = 2n - 2 >= 8$. .IP (ii) .I $mu = 6$ and $GAM$ is a half-cube. .IP (iii) .I $mu = 4$ and either $GAM$ is a Johnson graph or $GAM isom B(n)$ for some $n >= 2$. .IP (iv) .I $Ll ( GAM ) isom E sub 6$, $E sub 7$, or $E sub 8$. .Bop By Corollary 3.14.6, $GAM$ is locally connected, and by Proposition 3.14.1, $Ll ( GAM )$ is irreducible. Now we assume that we are not in case (iv). Then by Theorem 3.10.4, $Ll ( GAM )$ is isomorphic to $A sub n$ or $D sub n$; in particular $Ll ( GAM ) ib Zz sup {n+1} := Zz e sub 0 ds Zz e sub 1 ds ... ds Zz e sub n$, and we may identify vectors in $Ll ( GAM )$ with $( n + 1 )$-tuples of integers. .LP Suppose that $GAM$ contains points $gam , del$ at distance 2 such that the norm 4 vector $gam bar - del bar$ has the form $+- 2 e sub j$ for some $j$. Since $GAM$ is locally connected, it follows from Lemma 3.14.7 that $GAM ( gam ) ca GAM ( del ) = GAM ( gam )$. Therefore $GAM$ has valency $k = mu$, and $GAM$ is complete multipartite with classes of constant size $s$. But $GAM ( gam )$ has classes of size 1 or 2 only; therefore $s <= 2$, and $GAM isom K sub { m times 2 }$ for some $m >= 3$. If $m > 4$, then (i) holds; if $m = 4$ then $GAM$ is the halved 4-cube, and if $m = 3$ then $GAM isom J(4,2)$. [If we do not assume regularity, the conclusion here is that either $GAM$ is complete multipartite with classes of size 1 or 2, or $GAM isom K sub 3,1,1,1$.] .LP We may now assume that $GAM$ does not contain points $gam , del$ at distance 2 such that $gam bar - del bar = +- 2 e sub j$ $( j = 0 , ... , n )$. Fix $gam mo GAM$. By Proposition 3.14.8 we may assume that $del bar = sum del sub i e sub i$ with $del sub i mo "{"0,1"}"$ for all $i$ and $del mo GAM$, and that $gam bar = 0$. .br Now let $DELTA$ be the graph whose vertices are the $n + 1$ indices $0,1, ... ,n$, and whose edges are the pairs $ij$ such that some point of $GAM ( gam )$ is represented by $e sub i + e sub j$. Since distinct points of $GAM ( gam )$ are represented by distinct vectors (their difference must have norm 2 or 4) we may identify the point represented by $e sub i + e sub j$ with the edge $ij$ of $DELTA$. .br Let us denote by $S ( del )$ the set of indices $i$ with $del sub i != 0$. By Lemma 3.14.3, the points $del mo GAM sub 2 ( gam )$ are represented by norm 4 vectors $del bar = del bar - gam bar$, and these must have the form $e sub i + e sub j + e sub k + e sub l$, i.e., $S ( del )$ is a 4-set. The $mu$ common neighbours of $gam$ and $del$ are certain edges of the subgraph of $DELTA$ induced on $S ( del )$. By Lemma 3.14.9, the intersection $GAM ( gam ) ca GAM ( del )$ coincides with the set of edges of $DELTA$ contained in $S ( del )$, and $del mo GAM sub 2 ( gam )$ is uniquely determined by $S( del )$. To simplify the notation we shall use the abbreviation $abcd$ for a 4-set $"{" a , b , c , d "}"$. .LP Let us call a set $S ib "{" 0,1, ... ,n"}"$ .I special .R if there is a point $del mo GAM$ with .EQ C S ( del ) = S ,~~ d ( del , gam ) = 1o2 vb S vb . .EN Clearly, the empty set is special. Application of Lemma 3.14.3 to pairs of nonadjacent points in $GAM sub {<= 2} ( gam )$ yields the following facts (here distinct Latin letters denote distinct indices taken from $"{"0 , ... , n "}"$). .IP S1. If $del mo GAM sub 2 ( gam )$ then $S ( del )$ is special. .IP S2. If $abcd$ is special then precisely $mu$ of the sets $ab , ac , ad , bc , bd , cd$ are special. .IP S3. If $ab$ and $cd$ are special then precisely $mu$ of the sets $empty , ac , ad , bc , bd , abcd$ are special. .IP S4. If $abcd$ and $de$ are special then none or $mu$ of the sets $ad , bd , cd , abde , acde , bcde$ are special. .LP (Indeed, if $abcd$ and $de$ represent vertices at distance two, then they have $mu$ common neighbours, and these must be among the six sets listed. On the other hand, if one of these six sets is special, we must show that it represents a common neighbour of $abcd$ and $de$. But this follows immediately from Lemma 3.14.9.) .LP By definition, the edges of $DELTA$ are just the special 2-sets. Since $mu >= 3$, S3 implies that $DELTA$ has no subgraph consisting of two disjoint edges. Therefore $DELTA$ consists of a connected graph $DELTA sub 0$ and a (possibly empty) set of isolated vertices. S3 implies .IP S5. Any two disjoint edges of $DELTA$ have $mu - 1$ or $mu - 2$ transversals (i.e. edges meeting both given edges). .Xx "transversal of two edges" .LP Moreover, since $GAM$ is regular and not complete, $GAM ( gam )$ is not complete; therefore we have .IP S6. $DELTA sub 0$ is not isomorphic to $K sub 3$ or $K sub {s , 1}$. .LP We now consider each value of $mu$ separately. Clearly, S3 implies that $mu <= 6$. .SC Case 1: $mu = 6$. By S1 and S2, a point of $GAM sub 2 ( gam )$ is a complete subgraph $K sub 4$ of $DELTA sub 0$. Let $K$ be a complete subgraph $K sub m$ of $DELTA sub 0$ with maximal $m >= 4$. If $DELTA sub 0 != K$ then there is a vertex $b mo DELTA sub 0$ at distance 1 from $K$, and a vertex $a mo K$ adjacent with $b$. By maximality of $K$, there is a vertex $c mo K$ with $c nadj b$. Let $d mo K minus "{"a , c "}"$. Then the edges $ab, cd$ have at most 3 transversals, contradicting S5. Hence $DELTA sub 0 = K$ is complete and $GAM ( gam ) isom T(m)$. By Proposition 3.14.10 this determines the representation uniquely, and we find that $GAM$ is the halved $m$-cube. .SC Case 2: $mu = 5$. By S1 and S2, a point of $GAM sub 2 ( gam )$ is a subgraph $K sub {2,1,1}$ of $DELTA sub 0$. Let $K$ be a subgraph of $DELTA sub 0$ isomorphic to $K sub {m,1, ... ,1}$ with a maximal number $m +s$ of vertices, $m >= 2$, $s >= 2$. Using S5 we find as before that $DELTA sub 0 = K sub {m ,1, ... ,1}$. Let $L$ be the $m$-coclique of $DELTA sub 0$. If $s > 2$, then we find that, for $a, b, e mo K minus L$ and $c , d mo L$, the set $abcd$ is special. Now S4 gives a contradiction. Hence $DELTA sub 0 = K sub m,1,1$, and we find by Proposition 3.14.10 that $GAM isom K sub 1 ds T(m+2)$, but this graph is not regular. .SC Case 3: $mu = 4$. By S5, each pair of disjoint edges has 2 or 3 transversals. By S1 and S2, a point of $GAM sub 2 ( gam )$ is a special 4-set on which $DELTA sub 0$ induces .KS [diagram] .KE and by S3, all subgraphs of $DELTA sub 0$ of these shapes are special 4-sets. .br These subgraphs of $DEL sub 0$ are of the form $K sub 2,2$ and $K sub 1,3 + roman { edge }$. Let $E = A dotcu B$ be a largest subset of $DEL sub 0$ such that $a adj b$ for all $a mo A$ and $b mo B$, where $A$ and $B$ are nonempty. .br (i) .I $E$ contains all vertices of $DEL sub 0$. .R Indeed, if not then let $c mo DEL sub 0$, $c nm E$. We may assume $d(c,E) = 1$, say $c adj a mo A$. By maximality of $E$ there is a $b mo B$ such that $b nadj c$. Put $A sub 0 := A ca DEL (c)$ and $A sub 1 := A minus DEL (c)$, then for any $a mo A sub 0$ and $d mo A sub 1$ we have $a adj d$ since $a c$ and $b d$ have at least two transversals. But then $E cu "{" c "}" = A sub 0 dotcu (A sub 1 cu B cu "{" c "}" )$ is a larger subset of $DEL$ with the required property, contradiction. .LP (ii) .I $DEL sub 0$ does not contain a complete graph $K sub 4$ or a wheel $K sub 1,2,2$. .R Indeed, two disjoint edges in a $K sub 4$ have 4 transversals, which is impossible. If $DEL sub 0$ contains an induced subgraph $K sub 2,2,1$, say $a adj b adj c adj d adj a$, $e adj a,b,c,d$, then $abcd$ is special, and by S4 we find a contradiction. .LP (iii) .I $DEL sub 0$ is either complete bipartite or complete bipartite with one additional edge. .R Indeed, if $A$ contains two disjoint edges, then (since these must have at least two transversals) $A$ contains a triangle or a quadrangle, and since $B != empty$ this is forbidden by (ii). Thus, all edges in $A$ pass through one vertex $d$. If both $A$ and $B$ contain an edge then $DEL sub 0$ contains a $K sub 4$. So we may assume that $B$ is a coclique. If $vb B vb >= 2$ and $A$ contains two intersecting edges, then $DEL sub 0$ contains a $K sub 1,2,2$, contradiction. So we may assume that $B = "{"b"}"$. If $A$ has no isolated point, then we can move $d$ from $A$ to $B$ and are done. So we may assume that $A$ has at least two edges $c d$ and $d e$ and an isolated point $a$. Now S4 yields a contradiction. .LP (iv) .I If $DEL sub 0$ is complete bipartite, say $K sub s,t$, then $GAM isom J(s+t,t)$. .R Indeed, this follows from Proposition 3.14.10. .LP Now assume that $DEL sub 0$ is a complete bipartite graph $K sub s,t$ with one additional edge in the $t$-coclique, so that $GAM ( gam )$ is a grid $s times t$ with one additional vertex adjacent to a $s times 2$ subgrid. Let us temporarily call this latter graph $s sub "\(pl" times t$ - in the figure below the graph $3 sub "\(pl" times 4$ is drawn; a label $ij$ denotes the vector $u = e sub i + e sub j$. .KS [diagram] .KE .LP (v) .I If $GAM ( gam ) isom s sub "\(pl" times t$, then $t = s+1$, and $GAM isom B(s)$. .R Indeed, with Proposition 3.14.10 we find that $GAM isom B(s+t-2,s)$, and then regularity of $GAM$ implies $t = s+1$. .SC Case 4: $mu = 3$. By S5, each pair of disjoint edges has 1 or 2 transversals. By S1 and S2, a point of $GAM sub 2 ( gam )$ is a special 4-set on which $DELTA sub 0$ induces .KS [diagram] .KE .LP Assume first that $DELTA sub 0$ contains an induced path P of length 3 with vertices $a adj b adj c adj d$. By S3, $abcd$ is special. Let $e$ be at distance 1 from P. If $e adj d$, then S4 implies that precisely two of the sets $abde, acde, bcde$ are special. However, this is impossible: If $e adj a$, then $e adj b$ implies that $abde, bcde$ are not special. So $e nadj b$, and by symmetry $e nadj c$. But then $abde, acde$ and $bcde$ are all special, contradiction. And if $e nadj a$ then $e adj b$ since $ab$ and $de$ must have a transversal, and $e nadj c$ since $bc$ and $de$ cannot have 3 transversals. But then $acde$ and $bcde$ are not special, contradiction. Hence $e nadj d$, and by symmetry, $e nadj a$. .br If $e adj b$ and $e adj c$, then S4 with $( b , d )$ interchanged gives a contradiction. Therefore $e$ is adjacent to just one of $b$ and $c$ (and if $e adj b$ then $ebcd$ is special). Hence the neighbours $!= c$ of $b$ form a coclique $A$, and the neighbours $!= b$ of $c$ form a coclique $D$. Now it is easy to see that $DELTA sub 0 = A cu "{" b , c "}" cu D$ (the coclique extension of $P$ where $a$ and $d$ are blown up to $A$ and $D$, respectively). Since $gam$ has valency $vb A vb + vb D vb + 1$ and $bc$ has $X>= vb A vb + vb D vb + 2$ neighbours $gam$, $ab$ $( a mo A )$, $cd$ $(d mo D )$ and $P$, this contradicts the regularity of $GAM$. Therefore $DELTA sub 0$ does not contain an induced path of length 3. .br [If we do not assume regularity, this case leads to $GAM isom K sub 1 ds K sub { vb A vb + 1 , vb D vb + 1 }$.] .LP Now if $GAM sub 2 ( gam )$ contains a vertex $abcd$ with $b adj c adj d adj b$ and $e$ is adjacent with $d$, then $abcd$ and $de$ have only two common neighbours, contradiction. Hence $e nadj d$ and by symmetry, $e nadj b , c$. Therefore $bcd$ is an isolated triangle, $DELTA sub 0 = "{" b , c , d "}"$, contradicting S6. This shows that $GAM sub 2 ( gam )$ contains only special 4-sets forming a 3-claw. [If we do not assume regularity, this case leads to $GAM isom L(s,t)$, where $L(s,t)$ is the graph represented by $e sub i$ ($1 <= i <= 3s+t$), $e sub 3j-2 + e sub 3j-1 + e sub 3j$ ($1 <= j <= s$).] .LP Let $abcd$ be such a special 4-set, $a adj b, c, d$. If $e adj d$ then $e adj b, c$ since $DELTA sub 0$ has no path of length 3; but then S4 is violated. Hence $b, c, d$ are vertices of $DELTA sub 0$ of valency 1, and since $DELTA sub 0$ is connected and has no path of length 3, every vertex $!= a$ of $DELTA sub 0$ must be adjacent to $a$. By S6, $DELTA sub 0$ contains at least one further edge $ef$. If there is another edge $eg$ (or $fg$), then $ag,ef$ have 3 transversals, contradicting S5, and if there is another edge $gh$ then $ef,gh$ have no transversal, again contradicting S5. Therefore there is no further edge. Now $ef$ must have a neighbour in $GAM sub 2 ( gam )$, but there is no special 4-set containing $ef$, contradiction. Therefore $mu = 3$ is impossible. [If we do not assume regularity, then we find $GAM isom L(s,t)$ again.] .LP This completes the proof of the theorem. .Eop $Re$. .SC Koolen .[[ Koolen master's thesis 1990 .]] generalized this theorem by omitting `regular' from the assumptions. In the proof above we mentioned which further graphs arise in this more general situation. .bp Tables of parameter sets for bipartite (but not antipodal) distance-regular graphs with $v <= 4096$ that pass all known existence tests. .LP .Zh "Diameter 4 - Bipartite (but not antipodal) graphs" .br .Small These graphs are precisely the incidence graphs of partial $lambda$-geometries with nexus $e < k-1$ (i.e., excluding the symmetric nets), cf. Theorem 1.7.1. Apart from the families of generalized octagons of order $(1,t)$ (i.e., incidence graphs of generalized quadrangles of order $(t,t)$), and (pseudo) $D sub m (q)$ graphs, an infinite family of feasible $Q$-polynomial parameter sets with $k = 3 Binom(m,3) + Binom(m-1,2)$, $c sub 2 = Binom(m,2) - 1$, $c sub 3 = 3 Binom(m,3)$, $q sub 33 sup 3 = p sub 44 sup 4 = 0$ is visible. Such a graph is known only for $m = 4$ (and for $m = 3$ we get the 4-cube, which is antipodal). .nr aA \w'+ $v = 0000 = 1 + 000 + 000 + 0000 + 0000$' .de Bx .na .ti -10n .ds B; " .ie \\w'\\*(Bs'u+\\w'\\*(Ba'u-\\n(.lu+\\n(aAu+1n \{.ta \\n(.luR \\&\\*(Bk \\*(Bv \\*(Ba .br .ie \\w'\\*(Bs'u+\\w'\\*(Bp'u+\\n(aAu-\\n(.lu+1n \{.ta \\n(.lu-10nR \\*(Bs \\*(Bp\} .el \{.ta \\n(aAu-10nL \\n(.lu-10nR .ie \\n(aAu-12n-\\w'\\*(Bn'u-\\w'\\*(Bc'u \{\c .if !'\\*(Bn'' .if !'\\*(Bc'' .as Bn "; .as Bn \\*(Bc \\*(Bn \\*(Bs \\*(Bp .rm Bn Bc\} .el \{\c \\*(Bs \\*(Bp\}\} .br .if !'\\*(Bn'' \\*(Bn\c .if !'\\*(Bc'' .if !'\\*(Bn'' ; .if !'\\*(Bc'' \\*(Bc\} .el \{.ta \\n(aAuL \\n(.luR \\&\\*(Bk \\*(Bv \\*(Bs \\*(Ba .br .if !'\\*(Bp'' .if !'\\*(Bn'' .as Bn "; .as Bn \\*(Bp .if !'\\*(Bc'' .if !'\\*(Bn'' .as Bn "; .as Bn \\*(Bc .if !'\\*(Bn'' \\*(Bn\} .br .. .in 10n .so oo/IA4B.out .in 0 .ad n .Big