Algebraic Graph Theory

Preface

This note is mainly based on the book by Godsil and Royle, Algebraic Graph Theory. The section on Steiner systems follows the treatment in Rotman, An Introduction to the Theory of Groups.

For readers interested in further studies in graph theory, we refer to Bondy and Murty, Graph Theory with Applications, and for more advanced topics, to Diestel, Graph Theory. For permutation groups, a standard reference is Wielandt, Permutation Groups.

This note has been prepared with the assistance of AI software to help organize, clarify, and typeset the material. Additionally, SageMath software was used to construct, analyze, and visualize graphs (such as the Hoffman–Singleton graph, Petersen graph, Paley graphs, and Hamming graphs), and to compute automorphism groups and other combinatorial properties.

We hope these references and tools will help guide the reader to a deeper understanding of the material presented here.

Chapter 1 Graphs

A graph $X$ consists of a non empty vertex set $V(X)\neq\emptyset$ and an edge set $E(X)$, where each edge is an unordered pair of distinct vertices of $X$. We will usually write $xy$ instead of $\{x,y\}$ to denote an edge. If $xy\in E(X)$, then we say that $x$ and $y$ are adjacent or that $y$ is a neighbour of $x$, and we write $x\sim y$. A vertex is incident with an edge if it is one of the two vertices that form the edge.In this note, all graphs are finite, meaning that $V(X)$ is finite. Moreover, any two vertices determine at most one edge. In fact, the graphs we consider are simple graphs, that is, they have no loops and no multiple edges.

The degree of a vertex $v\in V(X)$, denoted $\deg(v)$, is the number of vertices adjacent to $v$, or equivalently, the number of edges incident with $v$. We define:

Graphs are often used to model binary relationships between objects. For example, $V(X)$ could represent computers in a network, with adjacency meaning that two computers are directly linked.

Graph isomorphisms

Two graphs $X$ and $Y$ are equal if $V(X)=V(Y)$ and $E(X)=E(Y)$. For most purposes, the structure of a graph does not change if the vertices are simply relabelled. This motivates the following definition.

Two graphs $X$ and $Y$ are isomorphic if there exists a bijection $\varphi:V(X)\to V(Y)$ such that $x\sim y$ in $X$ if and only if $\varphi(x)\sim\varphi(y)$ in $Y$. The map $\varphi$ is called an isomorphism, and its inverse is also an isomorphism. If $X$ and $Y$ are isomorphic, we write $X\cong Y$.

It is customary to represent a graph by a diagram, with points for vertices and lines for edges. Strictly speaking, these diagrams do not define a graph unless the vertex set is explicitly labelled. However, once the vertices are labelled, the diagram determines the graph up to isomorphism. The relative positions of the points and lines are irrelevant—the only information conveyed is which pairs of vertices are joined by edges.

Let $\varphi$ be an isomorphism from $X$ to $Y$. Then for every vertex $v\in V(X)$,

where $N_{X}(v)$ denotes the set of neighbours of $v$ in $X$.

Isomorphisms preserve degrees of vertices: if $\varphi:X\to Y$ is an isomorphism, then

From the proposition, $\varphi$ gives a bijection between $N_{X}(v)$ and $N_{Y}(\varphi(v))$. Thus $|N_{X}(v)|=|N_{Y}(\varphi(v))|$, which means $\deg_{X}(v)=\deg_{Y}(\varphi(v))$. ∎

Graph Isomorphism Problem (GI Open Problem)

Problem: Given two graphs, determine whether they are isomorphic, that is, structurally identical under some relabeling of vertices.

Despite its simple statement, there is no efficient algorithm known to solve it in general.

The current best algorithm is due to László Babai (2015), which uses group theory and graph automorphism groups to efficiently handle symmetries.

A graph is complete if every pair of distinct vertices is adjacent; the complete graph on $n$ vertices is denoted by $K_{n}$. A graph with vertices but no edges is called empty.

The complement of a graph $X$, denoted $\overline{X}$, is the graph with the same vertex set as $X$ but with edge set

That is, $\overline{X}$ contains exactly the edges not in $X$.

If $X$ is the empty graph on 3 vertices (no edges), then $\overline{X}=K_{3}$, the complete graph on 3 vertices.

As we said our graphs are simple graphs. A common generalisation is the directed graph (or digraph), used to model asymmetric relationships.

A directed graph $X$ consists of a vertex set $V(X)$ and an arc set $A(X)$, where each arc is an ordered pair of distinct vertices. In diagrams, arcs are drawn as arrows from the first vertex to the second.

Unless otherwise stated, all graphs in these notes are assumed to be finite, simple, and undirected.

1 Subgraphs

A subgraph $Y$ of a graph $X$ is a graph with $V(Y)\subseteq V(X)$ and $E(Y)\subseteq E(X)$.

If $V(Y)=V(X)$, then $Y$ is called a spanning subgraph of $X$. Any spanning subgraph can be obtained by deleting edges from $X$. The number of spanning subgraphs of $X$ is $2^{|E(X)|}$.

An induced subgraph of $X$ is a subgraph $Y$ where two vertices are adjacent in $Y$ if and only if they are adjacent in $X$. Equivalently, it is obtained by deleting vertices from $X$ (and all incident edges). The number of induced subgraphs of $X$ is $2^{|V(X)|}$.

A clique is a complete subgraph; an independent set is a set of vertices inducing no edges. The size of the largest clique in $X$ is the clique number $\omega(X)$; the size of the largest independent set is the independence number $\alpha(X)$.

Paths, connectivity, and cycles

A path of length $r$ from $x$ to $y$ is a sequence of $r+1$ distinct vertices beginning with $x$ and ending with $y$, such that consecutive vertices are adjacent. A graph is connected if there is a path between any two vertices; otherwise it is disconnected. A component of $X$ is a maximal connected induced subgraph.

Exercise: We have $\omega(X)=\alpha(\overline{X})$ and $\omega(\overline{X})=\alpha(X)$

Consider the graph $X$ with vertex set $\{1,2,3,4,5,6\}$ and edges $\{12,23,45\}$. This graph has three components:

123456 Exercise 1.1.1. Let $X$ be a simple graph with $n\geq 2$ vertices, and let $\overline{X}$ be its complement.

Show that if $X$ is disconnected, then $\overline{X}$ is connected.

Conclude that for any graph $X$ on $n\geq 2$ vertices, at least one of $X$ or $\overline{X}$ is connected.

Give an example of a graph $X$ such that $X$ is disconnected but $\overline{X}$ is connected.

A graph $X$ is connected if and only if it has exactly one component.

By definition, the components are maximal connected induced subgraphs partitioning $V(X)$. If $X$ is connected, the whole graph is one maximal connected induced subgraph, so it has one component. Conversely, if there is only one component, $X$ itself is connected. ∎

A cycle is a connected graph in which every vertex has degree $2$. The smallest cycle is $K_{3}$. A graph in which each vertex has at least two neighbours must contain a cycle.

An acyclic graph is a graph with no cycles, it is also called a forest. A connected forest is called a tree. A spanning tree is a spanning subgraph that is a tree.

A graph has a spanning tree if and only if it is connected.

If a graph has a spanning tree, it is clearly connected. Conversely, if $X$ is connected, start with $X$ and repeatedly delete edges from cycles until no cycles remain; the resulting subgraph is connected and acyclic, hence a spanning tree. ∎

Each edge contributes exactly $2$ to the total degree count, one for each endpoint. Summing over all edges yields the formula. ∎

Prove that a connected graph with maximum degree $\Delta(X)\leq 2$ is either a path or a cycle. In particular, if it is $2$-regular, it must be a cycle.

Prove that any connected graph with minimum degree $\delta(X)\geq 2$ contains at least one cycle.

Use the Handshaking Lemma to show that in any graph the number of vertices of odd degree is even.

Prove that the number of spanning subgraphs of a graph $X$ is $2^{|E(X)|}$.

Bipartite Graphs

A graph $X$ is bipartite if its vertex set $V(X)$ can be partitioned into two disjoint sets $U$ and $W$ such that every edge of $X$ connects a vertex in $U$ to a vertex in $W$. Equivalently, there are no edges between vertices within the same part.

The complete bipartite graph $K_{3,3}$ has vertex set partitioned into two sets of size 3 each, with every vertex in the first set connected to every vertex in the second set, and no edges within each set.

1. Let $P$ be a path (or cycle) in a graph. The length of $P$, denoted $|P|$, is the number of its edges. A cycle is called odd (even) if its length is odd (even).

2. Let $X$ be a connected graph, and let $u,v$ be vertices of $X$. The distance between $u$ and $v$, denoted $d_{X}(u,v)$, is defined by

Exercise: For any cycle, the number of vertices and the number of edges are equal.

A graph is bipartite if and only if it contains no odd cycles.

($\Rightarrow$) Suppose $X$ is bipartite with parts $U$ and $W$. Any cycle must alternate vertices between $U$ and $W$. Thus, the cycle length must be even (since it must return to the starting vertex in the same part after an even number of steps). So $X$ contains no odd cycles.

($\Leftarrow$) Suppose $X$ has no odd cycles. Pick any vertex $v$ and define:

If there were an edge within $U$ or within $W$, this would create an odd cycle (by combining the paths from $v$ to the two endpoints with that edge), contradicting the assumption. Therefore, $X$ is bipartite. ∎

2 Automorphisms of Graphs

An automorphism of a graph $X$ is an isomorphism from $X$ to itself. In other words, it is a permutation of the vertex set $V(X)$ that preserves adjacency: if $x\sim y$ in $X$, then $g(x)\sim g(y)$ for an automorphism $g$.

Then $Y^{g}$ is isomorphic to $Y$ and is also a subgraph of $X$.

The valency (or degree) of a vertex $x$ is the number of neighbors of $x$.

Let $N(x)$ be the subgraph induced by the neighbors of $x$. Then

Since $N(x)$ and $N(y)$ are isomorphic subgraphs of $X$, they have the same number of vertices, so $x$ and $y$ have the same valency. ∎

Thus, automorphisms permute vertices of equal valency among themselves.

A graph is called $k$-regular if every vertex has valency $k$. In particular, a $3$-regular graph is called cubic, and a $4$-regular graph is sometimes called quartic.

Distance and Automorphisms

The distance $d(x,y)$ between vertices $x$ and $y$ is the length of a shortest path connecting them.

Let $P=(x=v_{0},v_{1},\ldots,v_{k}=y)$ be a shortest path from $x$ to $y$ of length $k=d(x,y)$. Because $g$ is an automorphism, it preserves adjacency, so the image path

is a path of length $k$ from $g(x)$ to $g(y)$. Thus,

Automorphisms of the Complement

The complement $\overline{X}$ of a graph $X$ has the same vertex set, where two vertices are adjacent in $\overline{X}$ if and only if they are not adjacent in $X$.

Any automorphism preserves adjacency and non-adjacency, so it is also an automorphism of the complement. ∎

Examples of Automorphism Groups

Example Consider the graph $G$ with vertex set

This graph resembles a star centered at vertex 1 with edges $12,13,14$, plus edges $25$ and $35$ connecting vertices 2 and 3 to 5.

Observe that vertices 2 and 3 share identical neighborhoods:

The mapping that swaps vertices 2 and 3 (and fixes all other vertices) preserves adjacency, as: - edges $12$ and $13$ are swapped, - edges $25$ and $35$ are swapped, - vertices 1, 4, and 5 remain fixed.

Thus, the automorphism group of $G$ consists of the identity and the transposition swapping 2 and 3, and so

For $n\geq 3$, the automorphism group of the cycle graph $C_{n}$ is isomorphic to the dihedral group $D_{2n}$:

If an automorphism of $C_{n}$ fixes two adjacent vertices, then it must be the identity. Indeed, if $\varphi(v_{0})=v_{0}$ and $\varphi(v_{1})=v_{1}$, then adjacency forces $\varphi(v_{2})=v_{2}$, and inductively all vertices are fixed.

so that $\rho_{k}=(\rho_{1})^{k}$ in particular. Also define the reflection

From the above relations, $A$ is isomorphic to the dihedral group $D_{2n}$ and has exactly $2n$ elements: the $n$ rotations $\rho_{k}$ and the $n$ reflections $\rho_{k}\sigma$. For each $i,j$, there exists $k$ with $\rho_{k}(v_{i})=v_{j}$, namely $k\equiv j-i\pmod{n}$, so the rotations act transitively on $V$.

If instead $\varphi(v_{0})=v_{i}$ for some $i$, choose $k$ such that $\rho_{k}(v_{i})=v_{0}$. Then

Example[Path Graph $P_{n}$] The path graph $P_{n}$ has only two automorphisms: the identity and the "flip" reversing the path. Hence,

Example[Complete Bipartite Graph $K_{m,n}$] If $m\neq n$, then

where $S_{m}$ and $S_{n}$ are the symmetric groups on the two parts. If $m=n$, there is an additional automorphism swapping the two parts, so

3 Johnson, Petersen and Kneser Graphs

A particularly important family of graphs in algebraic and combinatorial graph theory are the $J(v,k,i)$ graphs. They provide a natural way to translate problems about finite sets into graph theory.

Let $v,k,i$ be integers with $v\geq k\geq i\geq 0$, and let $N$ be a fixed set of size $v$. The graph $J(v,k,i)$ is defined as follows:

The vertices are all $k$-element subsets of $N$.

Two vertices (subsets) are adjacent if and only if their intersection has size $i$.

Thus, $J(v,k,i)$ has $\binom{v}{k}$ vertices and is a regular graph.

Exercise Show that $J(v,k,i)$ has $\binom{v}{k}$ vertices and is a $d$-regular graph, where

A useful observation is that we may assume $v\geq 2k$:

Let $N$ be a fixed $v$-element set and $\binom{N}{k}$ be the set of all $k$-subsets of $N$ . Define a map

This map is clearly a bijection with inverse itself.

For any $k$-subsets $A,B\subseteq N$, we have

Hence, $|A\cap B|=i$ if and only if $\bigl|\varphi(A)\cap\varphi(B)\bigr|=v-2k+i$. This shows that $\varphi$ preserves adjacency in the Johnson graphs, so it is an isomorphism

When $v\geq 2k$, two special cases are of particular interest:

The most famous example is the Kneser graph $J(5,2,0)$, which is the Petersen graph.

Petersen Graph: Vertices are the $2$-element subsets of $\{1,2,3,4,5\}$. Two vertices are adjacent if and only if they are disjoint as sets.

$\{1,2\}<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo stretchy="false">{</mo><mn>3</mn><mo separator="true">,</mo><mn>4</mn><mo stretchy="false">}</mo></mrow><annotation encoding="application/x-tex">\{3,4\}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">{</span><span class="mord">3</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mord">4</span><span class="mclose">}</span></span></span></span></span>\{1,5\}<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo stretchy="false">{</mo><mn>2</mn><mo separator="true">,</mo><mn>3</mn><mo stretchy="false">}</mo></mrow><annotation encoding="application/x-tex">\{2,3\}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">{</span><span class="mord">2</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mord">3</span><span class="mclose">}</span></span></span></span></span>\{4,5\}<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo stretchy="false">{</mo><mn>3</mn><mo separator="true">,</mo><mn>5</mn><mo stretchy="false">}</mo></mrow><annotation encoding="application/x-tex">\{3,5\}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">{</span><span class="mord">3</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mord">5</span><span class="mclose">}</span></span></span></span></span>\{1,4\}<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo stretchy="false">{</mo><mn>2</mn><mo separator="true">,</mo><mn>5</mn><mo stretchy="false">}</mo></mrow><annotation encoding="application/x-tex">\{2,5\}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">{</span><span class="mord">2</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mord">5</span><span class="mclose">}</span></span></span></span></span>\{1,3\}$$\{2,4\}$ The Petersen graph is $3$-regular, has $10$ vertices and $15$ edges, and plays a central role in many areas of graph theory.

Automorphisms. If $g$ is a permutation of $N$ and $S\subseteq N$, define

Each such $g$ induces a permutation of the vertices of $J(v,k,i)$, and if $|S\cap T|=i$ then $|S^{g}\cap T^{g}|=i$, so $g$ is an automorphism of $J(v,k,i)$. Thus:

Open Problem: Determine all triples $(v,k,i)$ for which

That is, classify the parameters for which the automorphism group of a Johnson graph (or its Kneser graph special case) is isomorphic to the full symmetric group on $v$ vertices.

The automorphism group of the Petersen graph $P$ is isomorphic to $S_{5}$ in its natural action on the 2-subsets of $=\{1,2,3,4,5\}$.

We label the vertices of $P$ by the 2-element subsets of $$, with two vertices adjacent if and only if the corresponding subsets are disjoint.

Step 1: Structure of the Petersen graph in this labeling. The vertices can be divided into two 5-cycles:

The outer 5-cycle, consisting of vertices

where edges follow the cycle in that order (each consecutive pair is disjoint).

The inner 5-cycle, consisting of the remaining 2-subsets

again forming a 5-cycle in that cyclic order.

Step 2: Independent sets of maximum size. In any graph, an automorphism sends independent sets to independent sets of the same size. In a 5-cycle, the largest independent set has size 2. Since $P$ consists of two 5-cycles connected in a specific way, a maximum independent set in $P$ can contain at most two vertices from the outer cycle and at most two from the inner cycle. Hence:

and every maximum independent set has exactly two vertices from each cycle.

A simple example of a size-4 independent set is:

Clearly, there are exactly 5 such sets $I_{1},I_{2},I_{3},I_{4},I_{5}$, one for each element of $$.

Step 3: Classification of all maximum independent sets. Let $I$ be any independent set of size 4 in $P$. By Step 1, it must contain exactly two vertices from the outer cycle and two from the inner cycle.

The outer 5-cycle has a rotation symmetry given by the permutation

which acts on the 2-subset labels of $P$. By applying an automorphism corresponding to a rotation of the outer cycle, we can assume without loss of generality that:

Looking at the adjacency structure of $P$, the only way to complete $I$ to an independent set of size 4 is to take the inner vertices:

Hence, every maximum independent set is of the form $I_{j}$ for some $j\in$.

Any automorphism of $P$ permutes these sets, giving a homomorphism:

is a single vertex of $P$, so $g$ must fix this vertex. Since this holds for all pairs $j,k$, $g$ fixes every vertex of $P$, hence $g$ is the identity. Therefore:

An incidence structure is a pair $(P,\mathcal{B})$, where

$\mathcal{B}$ is a set of blocks (also called lines),

together with an incidence relation indicating which points lie in which blocks.

The Levi graph (or incidence graph) of an incidence structure $(P,\mathcal{B})$ is the bipartite graph with vertex set $P\cup\mathcal{B}$, where a point $p\in P$ is adjacent to a block $B\in\mathcal{B}$ if and only if $p$ is incident with $B$ (i.e., $p\in B$).

A polarity of an incidence structure $(P,\mathcal{B})$ is a bijection

$\pi$ maps points to lines and lines to points,

$\pi$ is an involution: $\pi^{2}$ is the identity, and

A configuration is self-dual if it admits a polarity. In other words, points and lines can be interchanged while preserving the incidence structure.

Remarks: A Levi graphs is bipartite, so Petersen graph is not a Levi graph.

In what follows, we present some classical examples of Levi graphs such as:

The Heawood graph which is the Levi graph of the Fano plane (self-dual configuration with 7 points and 7 lines).

4 The Tutte–Coxeter Graph (Tutte 8-cage)

A duad is a $2$-element subset of $\Omega$. Denote the set of duads by

A syntheme is a partition of $\Omega$ into three disjoint duads. Denote the set of synthemes by $S$, so $|S|=15$.

The Tutte–Coxeter graph $\Gamma$ is the bipartite incidence graph with parts $D$ and $S$, where $d\in D$ is adjacent to $s\in S$ if and only if $d\in s$.

The automorphism group of the Tutte–Coxeter graph is

Step 1. Side-preserving automorphisms. Any $\sigma\in S_{6}$ permutes the symbols of $\Omega$, thereby permuting duads and synthemes and preserving incidence. Thus

To see there are no additional side-preserving automorphisms, observe that from the graph $\Gamma$ alone we can reconstruct the six symbols of $\Omega$. For duads $a,b\in D$ define

Thus we can recognize within $\Gamma$ when two duads intersect. Construct a graph $X$ on $D$ where $a,b$ are adjacent iff $a\cap b\neq\varnothing$. Then for each $i\in\Omega$, the five duads containing $i$ form a clique $K_{5}$ in $X$, and these six cliques are exactly the maximal $5$-cliques in $X$. Hence the six symbols of $\Omega$ are canonically identifiable from $\Gamma$.

Therefore every automorphism of $\Gamma$ preserving the bipartition induces a permutation of the six cliques, i.e. an element of $S_{6}$. This proves

Step 2. Existence of a side-swapping automorphism.

We can show that the incidence structure $(D,S)$ is self-dual. However, the proof requires some group-theoretic machinery, in particular the existence of the exceptional outer automorphism of the symmetric group $S_{6}$. We leave this as an exercise, but we include below a brief sketch as a proposition.

In fact, there exists a polarity $\pi$ interchanging duads and synthemes while preserving incidence:

This polarity induces a graph automorphism $\tau$ of the Tutte–Coxeter graph satisfying

It is well known that $S_{6}$ has a unique nontrivial outer automorphism, and adjoining $\tau$ realizes this extension. Therefore

Let $\Omega=\{1,2,3,4,5,6\}$, let $D$ be the set of duads (2-subsets of $\Omega$) and let $S$ be the set of synthemes (partitions of $\Omega$ into three disjoint duads). Then there exists a bijection $f\!:D\to S$ which is a polarity of the duad–syntheme incidence structure; that is,

(2) Identifying duads and synthemes with permutations. Associate to each duad $d=\{a,b\}\in D$ the transposition $(ab)\in S_{6}$. Associate to each syntheme $s\in S$ the permutation $\tau_{s}\in S_{6}$ which is the product of the three disjoint transpositions that form $s$. Thus incidence $d\in s$ is equivalent to the transposition $(ab)$ being one of the three disjoint transpositions whose product is $\tau_{s}$.

(3) Define $f\colon D\to S$ via $\sigma$. For a duad $d=\{a,b\}$ let $t_{d}=(ab)$. Consider $\sigma(t_{d})$. By (1), $\sigma(t_{d})$ is a permutation of cycle type $2^{3}$; its three transposition factors correspond to a unique syntheme $s\in S$. Define $f(d)=s$. This produces a map $f\colon D\to S$.

(4) Well-definedness and bijectivity. If $t_{d_{1}}=t_{d_{2}}$ then $d_{1}=d_{2}$, so the assignment is well defined. The map $f$ is injective because $\sigma$ is injective and different transpositions land in different $2^{3}$-type elements (so give different synthemes). Since $|D|=|S|=15$, injectivity implies bijectivity.

(5) Incidence is reversed by $f$. Fix $d=\{a,b\}\in D$ and $s\in S$. Let $t_{d}=(ab)$ and let $\tau_{s}$ be the product of the three transpositions in $s$. Then

Apply $\sigma$ to both sides. Using that $\sigma$ is a homomorphism of the group structure (though outer, it still permutes conjugacy classes and respects products up to group law), we obtain that $\sigma(t_{d})$ is one of the three transpositions in the product $\sigma(\tau_{s})$. By the definition of $f$,

Therefore $f$ reverses incidence as required for a polarity.

Conclusion. The bijection $f$ (after the adjustment above if desired) is an incidence-reversing involution $D\leftrightarrow S$; i.e. a polarity of the duad–syntheme incidence structure. Hence the Tutte–Coxeter Levi graph is self-dual. ∎

where $d_{X}(u,v)$ is the length of the shortest path between $u$ and $v$.

Exercise 1. Show that the Johnson graph $J(v,k,i)$ has

Exercise 2. Show that the Petersen graph $P$ is connected and has diameter 3 and girth 5.

Girth 88 and diameter 44 of the Tutte–Coxeter graph

The Tutte–Coxeter graph $\Gamma$ has girth $8$ and diameter $4$.

Since $\Gamma$ is bipartite any cycle has even length; so the possible cycle lengths are $4,6,8,\dots$. We show no $4$- or $6$-cycle can occur; hence the shortest possible cycle is length $8$.

No $4$-cycles. Suppose there were a $4$-cycle

with $d_{i}\in D$ and $s_{j}\in S$. Then both synthemes $s_{1}$ and $s_{2}$ contain the two duads $d_{1}$ and $d_{2}$. But by construction of synthemes, two distinct duads determine at most one syntheme containing both. Therefore $\Gamma$ has no $4$-cycle.

No $6$-cycles. Suppose there were a $6$-cycle

Interpret this in the incidence structure: $d_{i}\in s_{i}$ and $d_{i+1}\in s_{i}$ (indices mod $3$). Pick the syntheme $s_{1}$ and the point (duad) $d_{3}$ not on $s_{1}$; then we should have a unique point on $s_{1}$ which is in a same syntheme with $d_{3}$ (collinear). But in the supposed $6$-cycle both $d_{1}$ and $d_{2}$ are points of $s_{1}$ that are collinear with $d_{3}$ (since the cycle gives paths $d_{3}-s_{3}-d_{1}$ and $d_{3}-s_{2}-d_{2}$), contradicting uniqueness. Hence no $6$-cycle exists.

With $4$- and $6$-cycles excluded, the smallest possible even cycle length is $8$ and we can see that there is 8-cycle.

Let $x,y$ be arbitrary vertices of $\Gamma$. We must show there is a path of length at most $4$ joining $x$ to $y$. Since $\Gamma$ is bipartite, distances between vertices in the same part are even and between opposite parts are odd; it therefore suffices to show that any two vertices of the same part are at graph-distance at most $4$ (this will imply the worst-case distance between arbitrary vertices is at most $4$).

Case A: $x,y$ are in different parts. Then either $x$ is adjacent to $y$ (distance $1$), or else there exists a neighbor $z$ of $x$ that is adjacent to $y$ giving a path of length $3$ at most. In fact if $x$ is a duad and $y$ a syntheme not incident to $x$, take any syntheme through $x$; there is a unique duad on that syntheme collinear with $y$, and that furnishes a path of length $3$. Thus distance between opposite parts is at most $3$.

Case B: $x,y$ lie in the same part. Without loss of generality assume $x,y\in D$ (duads). If $x$ and $y$ are both contained in a common syntheme then $\operatorname{dist}(x,y)=2$. Otherwise they are not collinear in the incidence structure; pick any syntheme $s$ incident with $x$. Then there is a unique duad $z\in s$ which is collinear with $y$. Hence we have the path

where $s^{\prime}$ is some syntheme containing both $z$ and $y$ (such $s^{\prime}$ exists because $z$ and $y$ are collinear). This is a path of length $4$ from $x$ to $y$. Thus any two duads are at distance at most $4$. The same argument applies when $x,y\in S$ (synthemes): if two synthemes are not adjacent, pick a duad on one and then we can find the unique duad to approach the other; this produces a length-$4$ path.

Combining the two cases we see every pair of vertices is at distance $\leq 4$, while examples of vertex pairs at distance exactly $4$ exist (e.g. certain pairs of duads that intersect), so the diameter is exactly $4$.

Therefore the Tutte–Coxeter graph $\Gamma$ has girth $8$ and diameter $4$, as required. ∎

5 The Fano Plane and the Coxeter Graph

Formally, it is an incidence structure $(\mathcal{P},\mathcal{L})$ where:

$\mathcal{P}=\{1,2,3,4,5,6,7\}$ is a set of 7 points.

$\mathcal{L}$ is a collection of 7 lines, each a 3-element subset of $\mathcal{P}$.

The incidence relation must satisfy the following axioms:

Any two distinct points lie on exactly one line.

Any two distinct lines intersect in exactly one point.

Each line contains exactly 3 points, and through each point pass exactly 3 lines.

A standard labeling satisfying these axioms is:

This structure can be visually represented by a diagram where points are dots and lines are smooth curves (often circles), with each line containing three points.

The lines are the 2-dimensional subspaces of $V$. A 2-dimensional subspace contains $(2^{2}-1)=3$ nonzero vectors, which are exactly the three nonzero vectors of the two 1-dimensional subspaces it contains. This explains why each line has 3 points.

Incidence is defined by containment: a point (1-subspace) lies on a line (2-subspace) if and only if the 1-subspace is contained in the 2-subspace.

This construction directly implies that the automorphisms of the Fano plane are induced by the linear symmetries of $V$.

Automorphism Group

Thus, the automorphism group of the Fano plane is a simple group of order 168. ∎

The Coxeter Graph

The Coxeter graph is a famous 3-regular (cubic) graph with 28 vertices and 42 edges. It is known for its high symmetry and interesting properties.

This construction is crucial for understanding the graph’s automorphisms.

Let $K(7,3)$ be the Kneser graph whose vertices are all 3-element subsets of a 7-element set $\mathcal{P}$ (the points of the Fano plane). Two vertices are adjacent if their corresponding subsets are disjoint. $K(7,3)$ has $\binom{7}{3}=35$ vertices.

Let $\mathcal{L}$ be the set of 7 subsets that are lines of the Fano plane. It is a set of 7 triples that Each pair of them has exactly one point in common.

Let $\mathcal{T}=\binom{\mathcal{P}}{3}\setminus\mathcal{L}$ be the set of 28 remaining 3-element subsets.

The Coxeter graph $\Gamma$ is defined as the induced subgraph of $K(7,3)$ on the vertex set $\mathcal{T}$. Two vertices in $\Gamma$ are adjacent if and only if their corresponding triples are disjoint.

Key Properties: Girth is 7 and Diameter is 4

No triangles (3-cycles) exist. Suppose $p,p^{\prime},p^{\prime\prime}$ formed a 3-cycle. Then by adjacency, fano plane should have 9 points a contradiction.

Suppose a 4-cycle exists: $T_{1}\sim T_{2}\sim T_{3}\sim T_{4}\sim T_{1}$, so that each consecutive pair is disjoint.

- Let $T_{1}\cap T_{3}$ and $T_{2}\cap T_{4}$ be examined. - Each triple has size 3, and consecutive triples are disjoint. Counting distinct points along the 4-cycle leads to at least $8$ points, but $\mathcal{P}$ has only 7 points. - Therefore, a 4-cycle is impossible.

Similarly, consider a hypothetical 5-cycle. Let $T_{1},\dots,T_{5}$ be the vertices.

- Consecutive triples are disjoint. - Counting points: each new triple adds at least one new point, but the total would exceed 7 points before closing the cycle. - Hence no 5-cycles exist.

The same argument works for a 6-cycle: consecutive disjoint triples would require $6\times 3/2\geq 9$ points (using overlaps carefully), again exceeding 7 points.

The Anti-Flag Construction and Automorphisms of the Coxeter Graph

Let $\mathcal{P}$ be the set of $7$ points of the Fano plane, and $\mathcal{L}$ the set of its $7$ lines. Denote by

the set of $28$ triples that are not lines of the Fano plane. The Coxeter graph $\Gamma$ is the induced subgraph of the Kneser graph $K(7,3)$ on the vertex set $\mathcal{T}$, where two triples $T,T^{\prime}\in\mathcal{T}$ are adjacent if and only if they are disjoint:

which is indeed a $3$-element non-line triple. Thus the vertices of $\Gamma$ can be identified with the $28$ anti-flags of the Fano plane.

Adjacency is inherited from the triple model:

Automorphisms

The automorphism group of the Fano plane is

of order $168$. Each automorphism $\sigma$ preserves incidence, so it acts naturally on anti-flags by

Therefore, every automorphism of the Fano plane induces a graph automorphism of $\Gamma$, giving

Example

6 The Heawood Graph

The Heawood graph $H$ is the bipartite Levi (incidence) graph of the Fano plane:

The Heawood graph $H$ has girth 6 and diameter 3.

The full automorphism group of the Heawood graph $H$ is

Step 1: Collineations of the Fano plane give automorphisms of $H$. The Heawood graph $H$ is the Levi graph of the Fano plane: its vertices are the 7 points together with the 7 lines, and adjacency means incidence in the Fano plane. Thus, any incidence-preserving permutation (collineation) of the Fano plane induces a permutation of the 14 vertices of $H$ that preserves adjacency. Therefore every collineation is a graph automorphism.

Step 3: Duality (polarity) of the Fano plane. The Fano plane is self-dual: there exists a bijection (called a polarity) that sends points to lines and lines to points, and preserves incidence. Applying such a polarity gives a permutation of the 14 vertices of $H$ that interchanges the two bipartite halves. This is again a graph automorphism.

Conjugating the 168 collineations by a polarity produces another 168 automorphisms, and together they form a group of size $168\cdot 2=336$.

Step 4: No further automorphisms. It remains to argue that $\operatorname{Aut}(H)$ cannot be larger. - First, note that the bipartition of $H$ (points vs. lines) is not preserved by every automorphism (because of the polarity), but the set of all 14 vertices is partitioned into two equal orbits under $\operatorname{Aut}(H)$. - The adjacency structure of $H$ uniquely encodes the incidence relation of the Fano plane. Hence any graph automorphism must send points to points or lines (via the polarity), and lines accordingly, so all graph automorphisms arise from collineations and possibly a polarity.

Thus, $\operatorname{Aut}(H)$ consists exactly of the $168$ collineations and their images under polarity, i.e. a group of size $336$.

Summary and Comparison

There is a clear link between the three objects: the Fano plane’s geometry gives rise to both the Heawood and Coxeter graphs, which share the same automorphism group. We note that a $(k,g)$-cage is a regular graph of degree $k$ and girth $g$ with the smallest possible number of vertices.

Definition

An $s$-arc in a graph $\Gamma$ is an ordered sequence of distinct vertices

such that $v_{i-1}$ is adjacent to $v_{i}$ for all $1\leq i\leq s$, and $v_{i-1}\neq v_{i+1}$ for all $1\leq i\leq s-1$ (that is, the path does not immediately retrace an edge).

A graph $\Gamma$ is $s$-arc-transitive if $\operatorname{Aut}(\Gamma)$ acts transitively on the set of all $s$-arcs (i.e. for any two $s$-arcs there exists an automorphism sending one ordered $s$-arc to the other).

Exercises

Show that the generalized Johnson graph $J(v,k,i)$, the Heawood graph, the Coxeter graph, $C_{n}$, and the Tutte–Coxeter graph are arc-transitive.