New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Chapter 6, Exercise 3(c) - Possibly wrong question #46
Comments
The lemma is indeed incorrect as stated. A feasible replacement (for the purposes of part (d)) would be:
|
@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. |
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". |
Need to fix Figure 6.20 to be undirected. |
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. |
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.
Consider the below (DFS) spanning tree for example:
Clearly vertex 1 has an edge with exactly one endpoint in T1, but vertex 1 is a cut vertex.
The text was updated successfully, but these errors were encountered: