Chapter 6, Exercise 3(c) - Possibly wrong question

[dipkakwani]

Please correct me if I am wrong, but I think the lemma asked to be proven in the exercise 3(c) of chapter 6 is incorrect.

Let T be an arbitrary spanning tree of G, rooted at an arbitrary vertex r. For each vertex v, let T_v denote the subtree of T rooted at v; for example, T_r = T . Prove that v is a cut vertex of G if and only if G does not have an edge with exactly one endpoint in T_v .

Consider the below (DFS) spanning tree for example:

Clearly vertex 1 has an edge with exactly one endpoint in T₁, but vertex 1 is a cut vertex.

[plin25]

The lemma is indeed incorrect as stated. A feasible replacement (for the purposes of part (d)) would be:

Let T be a DFS tree of G. Prove that the root of T is a cut vertex of G if and only if it has more than one child, and a non-root vertex v is a cut vertex of G if and only if no node in T_v with a back edge to a proper ancestor of v.

[jeffgerickson]

@plin25's suggested fix is incorrect: In @dipkakwani's example, 1 is a cut vertex, but there is a back-edge from 4 to 0.

[jeffgerickson]

The correct statement is "A non-root vertex v is a cut vertex of G if and only if v has a child w such that there is no edge in G between a descendant of w and a proper ancestor of v." Because the graph is undirected, any such edge must be a back edge. Equivalently: "...at least one descendant of each child of v is a neighbor of a proper ancestor of v".

[jeffgerickson]

Need to fix Figure 6.20 to be undirected.

[jeffgerickson]

Removed subproblem (b) ("find a cut vertex in a dag"). I don't know what I was thinking here; edge directions don't matter. I suppose I could ask how to find "(s,t)-cut vertices" in a dag, but that would be better as a separate question.

[jeffgerickson]

Added subproblem (b) back as a separate exercise. Time to move on.