# Let G be a connected graph in which every vertex has degree three. Show that if G has no cut-edge then every two edges of G lie on a common cycle.

"Let $$G$$ be a connected graph in which every vertex has degree three. Show that if $$G$$ has no cut-edge then every two edges of $$G$$ lie on a common cycle."

I have an idea for this proof but I'm not certain that I'm using Menger's theorem correctly. Menger's theorem states that the size of a minimum cut set is equal to the maximum number of disjoint paths that can be found between any pair of vertices

Suppose $$a,b,c,d \in V(G)$$, $$ab, cd \in E(G)$$

The graph is $$3$$-regular, so there can be at most $$3$$ edge disjoint paths between $$a$$ and $$d$$. Because the question tells us there is no cut-edge, we know the graph is at least two-connected, hence it is impossible to disconnect a and d by cutting only one edge. Can we not then immediately infer that by $$m$$-connectivity of $$G$$, $$m\geqslant 2$$, there must be at least two edge disjoint paths between any two vertices, and therefore any two edges $$ab$$, $$cd$$, will share a cycle that is composed of two edge-disjoint paths from $$a$$ to $$d$$, which together form a cycle?

• Two edge-disjoint paths need not form a cycle, because they might not be vertex-disjoint. The point of the 3-regular condition here is that for 3-regular graphs, the lack of a cut edge will imply the lack of a cut vertex, but you should actually prove this. Commented Dec 4, 2023 at 2:23
• (I guess you could also prove that any two edge-disjoint paths are also vertex-disjoint in the 3-regular case.) Commented Dec 4, 2023 at 2:35

As pointed out in the comments, the existence of vertex-disjoint paths does not imply the existence of edge-disjoint paths. However we can show that the absence of a cut-edge implies the absence of a cut-vertex: Assume that there exists a $$3$$-regular graph $$G$$ which has no cut-edge but has a cut-vertex $$v$$. When we remove the vertex $$v$$ and the edges incident to it, the graph $$G$$ falls into two or more components. As $$G$$ is $$3$$-regular, $$v$$ is connected to exactly three other vertices, say $$v_1,v_2,v_3$$, all having degree $$3$$ prior to the removal of $$v$$. After $$v$$ has been removed, $$v_1,v_2,v_3$$ all have degree $$2$$. As $$G$$ is split into multiple components, at least one of these vertices, say $$v_1$$, must be in a different component than at least one of the others, say $$v_2$$. The edge $$v$$-$$v_1$$ (or $$v$$-$$v_2$$ or $$v$$-$$v_3$$) was a bridge when $$V$$ was removed, connecting $$v_1$$ to that component. Therefore the deletion of $$v$$-$$v_1$$ disconnects $$G$$. But this is a contradiction since we said $$G$$ has no cut-edge.
Another method is to first see that $$G$$ has no loops; if it did, it would contain a cut-edge. Given the edge set $$E$$, consider two edges $$e_1, e_2 \in E$$ both with vertex-ends $$p_{1,2}$$, $$q_{1, 2}$$. If there exist vertex-disjoint paths from $$p_1$$-$$q_1$$ to $$p_2$$-$$q_2$$, then these paths along with $$e_1$$ and $$e_2$$ form a common cycle, and we are done. If these paths don't exist, then Menger's theorem (or at least the equivalent version in Diestel's book) implies that there is an order-$$1$$ separation $$(S_1, S_2)$$ where $$p_1, q_1 \in S_1$$ and $$p_2, q_2 \in S_2$$. Let $$s = S_1 \cap S_2$$ and $$r_1, r_2, r_3$$ be the other not necessarily distinct vertex-ends of edges incident to $$s$$. WLOG, $$r_1 \in S_1$$ and $$r_2, r_3 \in S_2$$. Then the edge $$r_1$$-$$s$$ is a cut-edge; contradiction.