In this problem, we consider the edge connectivity of a simple undirected graph, which is the minimum number of edges one can remove to disconnect it.

Prove that if G is a connected simple undirected graph where every vertex's degree is a multiple of 2, then one must remove at least 2 edges in order to disconnect the graph. (It should be noted that removing a vertex does not necessarily disconnect a simple graph.)

Does the statement above remain true if the number 2 is replaced with any positive integer k? If so, prove it. If not, give a counterexample.

Typically I would write where I am for a problem like this, but I have no idea how to approach this proof. Any and all help would be much appreciated.


$k$ is even
Assume that the edge connectivity is $1$, and we remove one edge to make the graph disconnected. Then, apart from the two end points of the removed edge, all vertices still have an even degree. Therefore, in each of the two connected components there is exactly one vertex of odd degree, and this violates the handshaking lemma (applied to a single connected component). Therefore we conclude that the edge connectivity cannot be $1$.

$k$ is odd:
Consider the complete graph on $k+1$ vertices (each vertex then has degree $k$). We shall add an additional vertex to it in order to construct a counterexample. Take all except $2$ of the vertices, and divide them into pairs. For each pair, take the edge between the two, and let it go through the new vertex instead of directly between the two vertces in the pair. The new vertex now has degree $k-1$, while all the other vertices still have degree $k$. Take two of these graphs, and add an edge between the two "new" vertices. You now have a graph of edge connectivity $1$, where each vertex has degree exactly $k$, and therefore degree divisible by $k$.


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.