In this post, we will be show how every 2-connected graph contains atleast one cycle.
First, we will discuss what exactly is a 2-connected graph. A connected graph is said to be 2-connected if it contains more than 2 vertices and the graph remains connected if fewer than 2 vertices are removed from the graph.
Example of 2-connected graph,
As you can see from the examples, if you remove less than 2 vertices from the graph, the graph remains connected. Removing 2 or more vertices may result in a disconnected graph.
Proof Every 2-Connected Graph Contains at least One Cycle
We will prove the statement by contradiction. Suppose a 2-connected graph G. Assume that G doesn’t contain any cycle. Graph G is connected and doesn’t contain any cycle. This implies that graph G is a Tree. But this is not possible. A tree can never be 2-connected. If we remove the parent of the leaf node from the tree, the tree becomes disconnected.
Thus, our assumption that a 2-connected graph doesn’t contains any cycle is wrong. This implies that every 2-connected graph must contain atleast one cycle. Hence Proved.
Read