[Solved]: Upper bound on the number of edges relative to the height of a DFS tree

Problem Detail: 

Let $T$ be a depth-first search tree of a connected undirected graph $G$ and $h$ be the height of $T$. How do you show that $G$ has no more than $h \times |V|$ edges where $|V|$ is the number of vertices in $G$?

Asked By : Shmoopy

Answered By : Chao Xu

After running a DFS, all the edges in $G$ can be classified as tree edges or back edges. Each back edge connects a vertex on the tree to one of it's ancestors. For each vertex it can point to at most $h-1$ ancestors, thus you can have at most $(h-1)|V|$ back edges. There are $|V|-1$ tree edges. You can have at most $h|V|-1$ edges.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12851

 Ask a Question

 Download Related Notes/Documents