What is the edge-connectivity and vertex-connectivity of the Petersen Graph

$\begingroup$

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.

$\endgroup$ 1

2 Answers

$\begingroup$

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:

$\endgroup$ $\begingroup$

This is a Labeled Petersen graph.Labeled Petersen graph

Now, when you remove the 3 edges which are connecting b from a, g and c, the new graph will look something like -

Disconnected Graph

Hope it helps.

PS- Unable to post Image directly due to some restrictions of StackExchange

$\endgroup$

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

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