6
$\begingroup$

Prove that if G is an undirected connected graph, then each of its edges is either in the depth-first search tree or is a back edge.

Now, from intuition and in class lectures by Steven Skiena, I know that the above holds true, since it dives all the way down, and then throw a rope back to a previous vertex. I also know that DFS is great in finding cycles.

However, my problem here is that I don't know how to prove that the edge is either a tree edge or a back edge.

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ You probably want to use induction. Start with a graph with one edge, then look at what happens in a larger graph, considering one edge and then applying induction to the remaining subgraph. $\endgroup$ – jmite Apr 20 '13 at 21:37
  • 2
    $\begingroup$ You can also argue for a contradiction - assume you have an edge that is neither, what would that imply? $\endgroup$ – Luke Mathieson Apr 21 '13 at 4:31
7
$\begingroup$

A depth first search on a directed graph can yield 4 types of edges; tree, forward, back and cross edges. As we are looking at undirected graphs, it should be obvious that forward and back edges are the same thing, so the only things left to deal with are cross edges.

A cross edge in a graph is an edge that goes from a vertex $v$ to another vertex $u$ such that $u$ is neither an ancestor nor descendant of $v$. So what you need to argue is that in an undirected graph, there's no way you can get a cross edge. It might help to think of why the can occur in directed graphs, and why you can't have this case in undirected graphs.

|cite|improve this answer
$\endgroup$
  • 2
    $\begingroup$ For cross-edges, you still need that the graph is assumed here to be connected. $\endgroup$ – Raphael♦ Apr 25 '13 at 14:28
  • 1
    $\begingroup$ @Raphael you don't really need the graph to be connected, you just need to rename tree edges as forest edges ;) - you still won't get cross edges. $\endgroup$ – Luke Mathieson Apr 26 '13 at 0:10
2
$\begingroup$

Let $G=(V,E)$ to be a graph and $u$ and $\nu$ to be its vertices such as $\in$ $V$ and $(u,\nu)\in E$.

Suppose that $u$ is discovered first. Consequently, its color is changed to gray. Then, $\nu$ becomes its descendant (by white path theorem) and the following discovery time relationship holds: $u.d<\nu.d$.

Depth-First Search graph example

Now, there are two options of discovering $(u,\nu)$ edge:

$\quad$ 1) if $u$ discovers $\nu$, then $(u,\nu)$ is a tree edge;

Depth-First Search graph, (u,v) is a tree edge

$\quad$ 2) if $\nu$ discovers $u$, then $(u,\nu)$ is a back edge since $u$ is still gray at the time the edge is first explored.

Depth-First Search graph, (u,v) is a back edge

|cite|improve this answer
$\endgroup$
-2
$\begingroup$

In the undirected graph we get only tree and back edges . the reason for no forward edges is because in undirected the forward edges get converted into back edges , it is so because in undirected there is no restriction in which direction to visit the vertex, so in case we have any vertex we can visit it from the child itself to the parent which counts as a back edge.

now lets talk of cross edge here also since edges are undirected so, the cross edges get converted to the tree edges as they can be visited as and when we go to any of that edge vertex for more details you can view this MIT vedio https://youtu.be/AfSk24UTFS8?t=36

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ I don't think this adds anything over the answer that is already there, apart from sloppy grammar and spelling. $\endgroup$ – Tom van der Zanden Oct 22 '15 at 20:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.