TAOCP 7.2.2.2 Exercise 447

Exercise 447. ▶ [22] [22] Determine the maximum number of edges in a girth-8 subgraph of $K_{8,8}$.

Verified: no
Solve time: 5m25s

Solution

Let the two parts of $K_{8,8}$ be $A$ and $B$, with $|A|=|B|=8$. A cycle in a bipartite graph alternates between the two parts, so a graph of girth at least $8$ contains neither a $4$-cycle nor a $6$-cycle.

A cycle of length $16$ gives a subgraph of $K_{8,8}$ with $16$ edges and girth $16$, so the maximum is at least $16$. It remains to prove that no girth-$8$ subgraph can have more than $16$ edges.

Suppose that a subgraph $G$ of $K_{8,8}$ has more than $16$ edges. The average degree of $G$ is

$$ \frac{2|E(G)|}{|V(G)|}>\frac{32}{16}=2. $$

Every graph with average degree greater than $2$ contains a subgraph with minimum degree at least $3$. Indeed, repeatedly delete vertices of degree at most $2$; if the process deleted every vertex, then the number of deleted edges would be at most twice the number of deleted vertices, giving $|E(G)|\leq |V(G)|$, contradicting $|E(G)|>16$. Let $H$ be a subgraph of $G$ with minimum degree at least $3$.

Choose any vertex $v$ of $H$. Since the girth of $H$ is at least $8$, the vertices encountered in a breadth-first search from $v$ through distance $3$ are all distinct except for the parent-child relationships in the search tree. The minimum degree condition forces the following numbers of vertices.

There are at least $3$ neighbors of $v$. These vertices lie in the part opposite $v$. Each of them has at least two further neighbors, because one neighbor is already used to reach it. Since a $4$-cycle is forbidden, these $3\cdot2=6$ vertices at distance $2$ from $v$ are distinct.

Each vertex at distance $2$ from $v$ has at least two further neighbors besides its predecessor. Since a $6$-cycle is forbidden, the resulting $6\cdot2=12$ vertices at distance $3$ from $v$ are distinct and none of them is among the vertices already counted.

If $v\in A$, then the vertices at distances $1$ and $3$ from $v$ all lie in $B$. Hence $B$ contains at least

$$ 3+12=15 $$

vertices. This contradicts $|B|=8$. The same contradiction occurs if $v\in B$.

Therefore no subgraph of $K_{8,8}$ with more than $16$ edges can have girth at least $8$.

The $16$-cycle construction gives a girth-$8$ subgraph with $16$ edges, and the preceding argument proves that a larger one cannot exist. Hence the maximum number of edges is

$$ \boxed{16}. $$