2-connected graph that is not 3-connected

2k Views Asked by At

So, I need to find 2 connected graph that is not 3-connected.

However, I think any 2-connected graph is not 3-connected since removal of two vertices make the graph disconnected.

Theorem says

Graph, $G$ , is $k$-connected if no set of $k-1$ vertices is separator of $G$

I am not really sure why I need condition for "not 3-connected"

1

There are 1 best solutions below

2
On

A graph being 2-connected just means that you need to remove at least 2 vertices to disconnect it. This means that a 3-connected graph is also 2-connected and a 2-connected graph could possibly be 3-connected. An example of a 2-connected but not 3-connected graph would be any cycle graph with at least 4 vertices.