What is the edge-connectivity and vertex-connectivity of the Petersen Graph?
I know the edge-connectivity and vertex-connectivity of the Petersen Graph is 3 but I am not sure how to prove it.
graph theory
What is the edge-connectivity and vertex-connectivity of the Petersen Graph?
I know the edge-connectivity and vertex-connectivity of the Petersen Graph is 3 but I am not sure how to prove it.
Best Answer
It easy to see that removing $3$ edges or $3$ vertices is sufficient to disconnect the Petersen graph as it is $3$-regular, so a single vertex can be isolated by removing its connected edges or adjacent vertices.
One advantage of the Petersen graph is that it is vertex-transitive, so any one vertex is indistinguishable, in graph property terms, from any other.
In particular deleting any vertex leaves a $9$-cycle (see diagram below and remove the central vertex) which thus cannot be broken with only one more removal of either edges or vertices. So removal of $3$ edges or vertices is also necessary to disconnect the graph.
This drawing of the Petersen graph from Wikipedia: