0
$\begingroup$

In three-connected graph $G = \langle V, E\rangle$, any three vertices $a,b,c \in V$ are contained in some simple cycle $C$ in $G$.

Please give some clues!

Thanks anyway!

1 Answers 1

1

The key to the proof is exploiting the fact that the graph is $3$-connected. This means that for any two vertices $x,y$ there are three disjoint paths between $x$ and $y$, i.e. three paths that pairwise share no vertices.

Given your three vertices $a$, $b$ and $c$, you should be able to use this to construct a cycle. A good start might be to sketch a little diagram, and see how the $3$ sets of paths (between $a$ & $b$, $b$ & $c$ and $c$ & $a$) can intersect, and how you might construct a cycle from these.