Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I got this question, and I'd be happy for help.

G=(V,E). $G_S$ is a Strongly-Connected Components's Graph.

I need to prove, that if there is only one Component ($C_0$) which is not with incoming edge, that there is a DFS running in G that ruturn one tree, and only him.

I thought to start from the vertex with the lattest finish time in $C_0$. It works on my examples, but I dont know how to prove it, and if it is correct.

Thank you for your help.

share|cite|improve this question
Think of that Component as being the source of your graph. Also, think of each CC (Connected Component) as being it's own vertex in a graph. – Nicolas Villanueva May 3 '11 at 10:16
@Nicolas Villanueva: Thank u, but I didn't understand What do you mean about thinking of each CC (Connected Component) as being it's own vertex in a graph? CC is composed from many vertex of the graph G. Do you talk about $G$ or G_s$? – Amir May 3 '11 at 11:48
@Amir Yes each individual CC is a set of vertices, but you can combine the vertices into 1 vertex. For example, look at Figure 2 of on page 2. – Nicolas Villanueva May 3 '11 at 11:58
@Nicolas Villanueva: sorry, but I still don't understand how it helps me. The Graph $G_s$ is given, and I need to prove that there is DFS running on G. Now, How it helps me to combine all the vertex to CC in G? I need to prove for each CC that there is only one tree from DFS's scanning? – Amir May 3 '11 at 12:20
@Amir Yes. If you contract all CC's so they are represented by a single vertex, then only one of those contracted vertices will not have an in-deg = 0, this will be your source/starting vertex for DFS. I have finals in about an hour, but that should hopefully get you started in the correct direction – Nicolas Villanueva May 3 '11 at 15:18

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.