vertices on a path

Question

Let $G = (V,E)$ be a graph on at least $3$ vertices so that for every vertex $v in V, Gbackslash v$ is connected. Prove that for any vertices $u$ and $v,$ there is a cycle containing $u$ and $v$.
I would prefer not to use Menger's Theorem (if so, then I could claim that since the minimum separator for $u$ and $v$ has length at least $2$, there are $2$ vertex-disjoint disjoint paths from $u$ to $v$ and hence $u$ and $v$ are contained in the same cycle). I think I can show that each edge of $G$ is contained in a cycle. I'm thinking of showing by induction on the length of a shortest path $P$ from $u$ to $v$ that every vertex $P$ in the path is in a cycle containing $u$. For the inductive step, I suppose the shortest path would have length $0$. Then $u=v,$ which is part of an edge in $G$ and thus contained in a cycle. Assume that for all shortest paths between $u$ and $v$ of length less than $kgeq 1,$ every vertex in the path is contained in a cycle that contains $u$. I'm not sure how to proceed with the inductive step.

Morgan Rodgers · Answer

This is a nice proof due to the (undergraduate) book by Bondy and Murty (Theorem 3.2)
I will use the fact that for a nontrivial graph, if the graph is $2$-connected, then the graph is at least $2$-edge-connected; this means that if the graph cannot be disconnected by removing a single vertex, then it cannot be disconnected by removing a single edge either (this is good to prove as an exercise).
We will use induction on $d(u,v)$. I will use the base case of $d(u,v) = 1$; if $d(u,v) = 1$, then if $e$ is the edge joining $u$ and $v$, $G-e$ is connected; so there is a $(u,v)$-path in $G-e$ which, together with $e$, gives a cycle containing $u$ and $v$.
Now we will assume that this holds for any two vertices at distance less than $k$, and assume that $d(u,v) = k geq 2$. Consider a $(u,v)$-path of length $k$, and let $w$ be the vertex that preceeds $v$ on this path. Now $d(u,w) = k-1$, so there is a cycle containing $u$ and $w$; we will consider this cycle $P cup Q$ where $P$ and $Q$ are internally disjoint $(u,w)$-paths. Furthermore, $G-w$ is connected so there is a $(u,v)$ path $P^{prime}$ not containing $w$. Let $x$ be the last vertex in $P^{prime}$ that is also in $P cup Q$; without loss of generality we can assume that $x in P$.
Now we get a cycle containing $u$ and $v$ by following $P$ from $u$ to $x$; following $P^{prime}$ from $x$ to $v$; the edge $vw$; and then $Q$ from $w$ to $u$ (technically I guess we are traversing the path $Q$ backwards).

vertices on a path

One Answer

Add your own answers!

Ask a Question