I have been working on some problems within introductory graph theory, and I ran
into one problem that I am having difficulty trying to prove. I want to
prove that a $2$-connected graph contains a cycle. Note that a $k$-connected
graph is a graph that contains at least $k+1$ vertices, but does not contain a
set of $k-1$ vertices whose removal disconnects the graph.
Hence, let us consider a graph $G$ such that $|V(G)| \geq 3$ such that there
is no cut set of size $1$. I imagine what I am looking to force onto this
graph is a cycle of size $3$, and thus I should probably condition on all
vertex subsets of size $3$ in the graph $G$. I tried finding a contradiction
after I assume that none of these subsets contained an odd cycle, but I
haven't been able to contradict $2$-connectedness with this statement.
Is it possible that I should condition on a single
vertex, and find a way to construct a cycle using the fact that this
vertex does not have the ability to disconnect the graph after its removal?
Best Answer
Pick a vertex $u$ with at least two neighbors, call them $v$ and $w$. Since $G$ is $2-$ connected there is a path from $v$ to $w$ that does not include $u$. Let $v=x_1,x_2\dots x_n=w$ be such a path. Notice that $x_1,x_2\dots x_n,u,v$ is a cycle.