Contracting¶

Example¶

For an example with this number of edges, you can place one vertex in the center of the graph and, for every two other vertices, construct a triangle that includes this central vertex.

Proof of Maximality¶

Here, we prove by induction that in any graph whose cycles do not share edges, \(2m \le 3n-1\) holds true. Consider the smallest counterexample to this theorem. This graph cannot be acyclic because in that case, the number of its edges would be less than its vertices, meaning the statement would hold for it. It is clear that the cycles in this graph cannot have chords (i.e., there are no edges within them) because that would create two cycles sharing an edge. Also, a single vertex cannot be adjacent to two vertices of the same cycle. Therefore, we contract one of the cycles in this graph. The graph remains simple, and it can be shown that its cycles still do not share edges. (Prove this statement to gain intuition about contraction.) And since we considered the smallest counterexample, the statement holds in the new graph. If we contracted a cycle of length \(k\), then \(k\) edges and \(k-1\) vertices are removed from the graph. So we have:

And we already knew that:

From these two statements, we deduce that:

This implies that the cycle we removed had fewer than 3 vertices, which is impossible in simple graphs. From this, we reach a contradiction. With a little care, it can be seen that equality occurs only when \(k\) is exactly 3, which means all cycles in the graph are triangles (as was the case in our example).