Finding the girth of a graph and proving it is the correct one I have to find the girth $g$ of the graph below and prove that the girth is at least $g$ and at most $g$. Clearly this graph has no cycle of length $1$ or $2$ since it is simple, so $g \geq 3$. There is no clique of size $3$ thus there is no triangle. But we can find a cycle of length $4$. Is the justification enough for $g \geq 4$? What can I do to show the other inequality? ![G](

Finding a cycle of length $4$ is a proof that the girth is at most $4$. The girth is the length of the shortest cycle, and we've found a cycle of length $4$, so either that's the shortest cycle, or there is an even shorter cycle than that.

To prove the girth is at least $4$, we need to rule out all shorter cycles. This graph is small, so we can just check directly that no $3$-cycles exist by trying all the possibilities. Another approach for this graph is to show that the graph is bipartite, as evidenced by the coloring below:

![2-coloring](

(The red vertices are one part, the blue vertices are the other.) There can be no odd cycles in a bipartite graph, so in particular there are no $3$-cycles.