Edges on a common cycle
Task number: 3968
Show that every conneected graph on at least three vertices is 2-connected if and only if:
Variant
Every two edges lie on a common cycle.
Hint
Reduce the problem into a similar statement about vertices.
Solution
Forward implication:
Note that a connected graph on at least three vertices contains at least two edges, so we quantify over a nonempty set.
We subdivide the two given edges, each by an extra new vertex. We know that this operation and the inverse operation maintain 2-connectivity. On the added vertices we apply a theorem about two vertices on a common cycle. The cycle must use both pairs of edges created by the division. By removing the added vertices, we return the graph to its original state and obtain a cycle that passes through the prescribed edges.
Backward implication:
Because the graph is connected and has at least two edges, it has no isolated vertices. It also has no vertices of degree one, because the corresponding edge would not be able to lie on any cycle. Thus, if two vertices \( u \) and \( v \) are given, two different edges can be selected, the first incident with \( u \) and the second incident with \( v \). A cycle that contains selected two edges also contains the given vertices. This procedure can be performed for each pair of vertices, so the graph is 2-connected.
Variant
Every two adjacent edges lie on a common cycle.
Solution
The forward implication follows directly from the previous variant, because the current condition is only a special case of it.
Conversely, if the graph had an articulation \( u \), then the edges leading from \( u \) to the various components of \( G-u \) could not appear on a common cycle, since then \( u \) was not an articulation.
