2
$\begingroup$

"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?

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Dec 4, 2023 at 2:23
  • 1
    $\begingroup$ (I guess you could also prove that any two edge-disjoint paths are also vertex-disjoint in the 3-regular case.) $\endgroup$ Dec 4, 2023 at 2:35

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .