= Solution
In <depth-first search> of an <undirected graph>, every <edge> joins a <vertex> to one of its ancestors or descendants in the discovery <tree>. To see this directly, suppose $u$ is discovered before its neighbour $v$. If $v$ is still undiscovered, the search from $u$ cannot finish before discovering $v$: it eventually scans $uv$. Thus $v$ is discovered while the call for $u$ remains active and belongs to its descendant <subtree>.<Depth-first search by Jeff Erickson>[Chapter 6, §6.1: active recursion intervals, tree/back edges and ancestor relations]{ref}
For any <edge> $uv$, its ancestor endpoint therefore has a proper descendant and hence at least one child. It is an <internal vertex of a rooted tree>. \b[Every <edge> has an internal endpoint], so the internal <vertices> form a <vertex cover>. The relevant <leaves of a rooted tree> here have no children in the rooted discovery <tree>; a root of <vertex degree> one can still be internal.
Back to article page
