2
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.