$\begingroup$

I was given this "prove/disprove" question:

• Given a connected undirected graph, a vertex v in is called a cut-vertex if removing v and all its adjacent edges results in an unconnected graph. Let
  G=(V,E) be a graph that has no cut-vertices. For every vertex u∈V, if DFS(u) is performed, then in the resulting spanning tree, deg(u)=1

I have the understanding why this is true, what \i'm lacking is how to prove it.

$\endgroup$

1 Answer

$\begingroup$

How about something along the lines of a contradiction argument:

Assume that I have some vertex, q, in V with degree > 1 after performing a DFS(q). This implies that there is at least one pair of vertices in my graph G only reachable through q, since DFS would exhaust all possible paths before returning to q. This then implies that if I were to remove q, I would have a disconnected graph because q would be a cut-vertex. Since this contradicts the given that G has no cut-vertices, my assumption regarding q must be false. Therefore, there are no vertices in the spanning tree with degree > 1. I hope this helps.

$\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