Explain why a bipartite graph that doesnt contain a C4 canno

Explain why a bipartite graph that doesn\'t contain a C_4 cannot be C_4-saturated.

Solution

We know that Ck-saturated graphs can be viewed by generalizing the Moore graphs of diameter 2, but reflected. We also know that the structure and techniques of Ck-saturated graphs are quite similar to the eigenvalue approach used to prove both the Hoffman-Singleton result on Moore graphs and the Friendship Theorem, which states that a graph in which any two distinct vertices have exactly one common neighbor has a vertex adjacent to all others. Structural arguments are used to prove that under certain conditions the graphs are regular. Counting of walks then provides a polynomial equation involving the adjacency matrix, after which eigenvalue arguments exclude all but a few graphs. Also, the graphs that result from the Friendship Theorem consist of some number of triangles sharing a single vertex; such graphs are uniquely C5-saturated. Thus, unlike for C4, there are infinitely many uniquely C5-saturated graphs.

There are exactly 10, C4-saturated graphs. K1, K2 and K3 are C4-saturated. C5 is another C4-saturated graph when girth is 5. There are 6, C4-saturated graphs when girth is 3. Therefore, in total there are 10, C-4 saturated graphs. Now if a bipartite graph doesn\'t have C4, it won\'t meet either of these 10 conditions, hence it cannot have a C4-saturated graph.