<p>First note that #2 and #3 are saying the same thing. Next, notice that if <code>u</code> is an ancestor of <code>v</code> in <code>T</code>, then in a pre-order traversal, we see <code>u</code> before <code>v</code>, and therefore <code>pre(u) &lt; pre(v)</code>. On the other hand, since <code>T</code> is a depth-first search tree (as opposed to an arbitrary tree) of the connected undirected graph <code>G</code>, and $(u,v) \in G-T$, we can deduce that <code>pre(u)&lt;pre(v)</code> results in <code>u</code> being an ancestor of <code>v</code>.</p>

<p>The following image, taken from Wikipedia, can help:</p>

<p><img src="https://upload.wikimedia.org/wikipedia/commons/thumb/6/67/Sorted_binary_tree.svg/500px-Sorted_binary_tree.svg.png"/></p>

<p>Preorder traversal sequence: F, B, A, D, C, E, G, I, H (root, left, right)</p>

<p>Postorder traversal sequence: A, C, E, D, B, H, I, G, F (left, right, root)</p>

CC BY-SA 2.5
2010-09-27T07:11:57.223Z
Yeah, was able to figure out the first part on my own. The problem with the second part is that I don't see how it would be *necessary* that $u$ be an ancestor of $v$. Doesn't my counter-example for #2 show that that statement isn't necessarily true for the conditions they've supplied?
Jake
CC BY-SA 2.5
2010-09-27T07:17:20.750Z
Regarding the image you've attached - take vertices $A$ and $D$. $pre(A) < pre(D)$, but $A$ is not an ancestor of $D$.
Jake
CC BY-SA 2.5
2010-09-27T07:17:32.170Z
Have you noticed the sentence `Let (u,v) be an edge in G that is not in T` at the beginning of the question?
Sadeq Dousti
CC BY-SA 2.5
2010-09-27T07:23:08.880Z
Yes, but I'm not clear on how it impacts the question other than specifying that $u$ and $v$ aren't adjacent. Is that the key to this? Can you elaborate a bit more?
Jake
CC BY-SA 2.5
2010-09-27T07:32:48.337Z
@Jake: I'm very sorry if my explanation isn't clear. Yet I don't know how to clarify it more, since it seems obvious to me. Fortunately, there's a workaround (an intuition, not a proof): Try drawing a graph G as described by the problem, such that in its depth-first tree `T`, we have $(u,v) \in G-T$ and  `pre(u)<pre(v)`, but it violates the `u is v's ancestor` condition. If you succeed, send the link to the graph's image, and then I will know where the problem lies. Otherwise, you'll get a clear intuition as why it is correct.
Sadeq Dousti
CC BY-SA 2.5
2010-09-27T07:36:50.100Z
@Sadeq: In the image you posted, consider vertices $A$ and $D$. These satisfy the conditions that $pre(A) < pre(D)$ and $A$ is not an ancestor of $D$. Define the graph $G$ as $T$ with the additional edge $(u,v)$. Now $(u,v)\in G-T$, and we have constructed a valid counter-example. I am very interested in understanding what is wrong with this counter-example, so please tell me where the hole is.
Jake
CC BY-SA 2.5
2010-09-27T07:48:07.833Z
@Sadeq: Please see my updated question description for details. Thank you for your help so far!
Jake
CC BY-SA 2.5
2010-09-27T08:34:41.593Z
@Jake: The DFS of the graph you depicted is: F-B-A-D-C-E-G-I-H. Then, the edge (A,D) is in T, and the premise of the problem is NOT satisfied. I advise you to review DFS: http://en.wikipedia.org/wiki/Depth-first_search
Sadeq Dousti
CC BY-SA 2.5
2010-09-27T13:40:16.353Z
@Sadeq: Ok, I was confused about the depth-first search part. I hadn't heard of the concept of applying a depth-first search to a general graph to generate a tree. Thank you again for your help.
Jake
CC BY-SA 2.5
2010-09-27T14:57:36.077Z
@Jake: I'm very happy I was able to help.
Sadeq Dousti
CC BY-SA 2.5
2010-09-27T07:10:24.487Z
2010-09-27T10:44:11.240Z
2017-03-09T18:04:14.323Z
Sadeq Dousti
<p>The following is from this year's CS GRE practice test. I've worked through the test and I've been able to understand every question except for this one. Can anyone help me understand what's going on here?</p>

<blockquote>
  <p><b>Question:</b> </p>
  
  <p>Let $T$ be a depth-first search tree of a connected undirected graph $G$. For each vertex $v$ of $T$, let $pre(v)$ be the number of nodes visited up to and including $v$ during a preorder traversal of $T$, and $post(v)$ be the number of nodes visited up to and including $v$ during a postorder traversal of $T$.</p>
  
  <p>The lowest common ancestor of vertices $u$ and $v$ in $T$ is a vertex $w$ of $T$ such that $w$ is an ancestor to both $u$ and $v$, and no child of $w$ is an ancestor of both $u$ and $v$.</p>
  
  <p>Let $(u,v)$ be an edge in $G$ that is not in $T$, such that $pre(u) &lt; pre(v)$. Which of the following statements of $u$ and $v$ must be true?</p>
  
  <ol>
  <li>$post(u) &lt; post(v)$</li>
  <li>$u$ is an ancestor of $v$ in $T$.</li>
  <li>If $w$ is the lowest common ancestor of $u$ and $v$ in $T$, then $w = u$.</li>
  </ol>
</blockquote>

<p>I'm not going to post the answer just yet. If you're interested, it's available in the PDF:</p>

<p><a href="http://www.ets.org/Media/Tests/GRE/pdf/CompSci.pdf" rel="nofollow noreferrer">http://www.ets.org/Media/Tests/GRE/pdf/CompSci.pdf</a></p>

<p>I think that none of these can be true, based on the following:</p>

<ol>
<li>If $u$ is an ancestor of $v$ and $v$ is a leaf, then this would be false because leaves are counted first by postorder traversal.</li>
<li>If $u$ is a left sibling of $v$, then $u$ is counted first by preorder traversal, but $u$ is clearly not an ancestor of $v$.</li>
<li>This statement is equivalent to #2, and could be false by the same argument.</li>
</ol>

<p>I think it goes without saying that the test answers say I'm wrong about this. Am I missing something here? Can anyone provide an explanation as to why I'm wrong, as well as how to arrive at the correct answer?</p>

<p>Thanks!</p>

<p><strong>EDIT:</strong></p>

<p>Per Sadeq's request, I've included a counter example to #2/#3:</p>

<p><a href="http://img39.imageshack.us/img39/6410/counterexample.png" rel="nofollow noreferrer">Counter Example http://img39.imageshack.us/img39/6410/counterexample.png</a></p>

<p>The graph $G$ is shown in the image. If we remove the edge between $A$ and $D$, then we get the tree $T$. Now we have the following:</p>

<ol>
<li>$(u,v)\in G - T$</li>
<li>$pre(A) &lt; pre(D)$</li>
<li>$A$ is not an ancestor of $D$ in $T$.</li>
</ol>

CC BY-SA 2.5
2010-09-27T11:35:07.303Z
Your illustration is not a depth-first search tree for this particular graph. Try it, run a depth-first search and see what happens.
Jukka Suomela
CC BY-SA 2.5
2010-09-27T11:45:31.480Z
@Jukka: Yeah, I discussed that below. @Jake: Please see the discussion which I believe is clarifying.
Sadeq Dousti
<graph-theory>
Pre-order traversal on a search tree
Jake
# Pre-order traversal on a search tree

(Asked by: username_0 on 2010-09-27)

The following is from this year's CS GRE practice test. I've worked through the test and I've been able to understand every question except for this one. Can anyone help me understand what's going on here?

> **Question:**
>
> Let $T$ be a depth-first search tree of a connected undirected graph $G$. For each vertex $v$ of $T$, let $pre(v)$ be the number of nodes visited up to and including $v$ during a preorder traversal of $T$, and $post(v)$ be the number of nodes visited up to and including $v$ during a postorder traversal of $T$.
>
> The lowest common ancestor of vertices $u$ and $v$ in $T$ is a vertex $w$ of $T$ such that $w$ is an ancestor to both $u$ and $v$, and no child of $w$ is an ancestor of both $u$ and $v$.
>
> Let $(u,v)$ be an edge in $G$ that is not in $T$, such that $pre(u) < pre(v)$. Which of the following statements of $u$ and $v$ must be true?
>
> 1. $post(u) < post(v)$
> 2. $u$ is an ancestor of $v$ in $T$.
> 3. If $w$ is the lowest common ancestor of $u$ and $v$ in $T$, then $w = u$.

I'm not going to post the answer just yet. If you're interested, it's available in the PDF:

<http://www.ets.org/Media/Tests/GRE/pdf/CompSci.pdf>

I think that none of these can be true, based on the following:

1. If $u$ is an ancestor of $v$ and $v$ is a leaf, then this would be false because leaves are counted first by postorder traversal.
2. If $u$ is a left sibling of $v$, then $u$ is counted first by preorder traversal, but $u$ is clearly not an ancestor of $v$.
3. This statement is equivalent to #2, and could be false by the same argument.

I think it goes without saying that the test answers say I'm wrong about this. Am I missing something here? Can anyone provide an explanation as to why I'm wrong, as well as how to arrive at the correct answer?

Thanks!

**EDIT:**

Per Sadeq's request, I've included a counter example to #2/#3:

[Counter Example http://img39.imageshack.us/img39/6410/counterexample.png](http://img39.imageshack.us/img39/6410/counterexample.png)

The graph $G$ is shown in the image. If we remove the edge between $A$ and $D$, then we get the tree $T$. Now we have the following:

1. $(u,v)\in G - T$
2. $pre(A) < pre(D)$
3. $A$ is not an ancestor of $D$ in $T$.

**Tags:** graph-theory

> **Comments:**
> **username_1**: Your illustration is not a depth-first search tree for this particular graph. Try it, run a depth-first search and see what happens.  
> **username_2**: @Jukka: Yeah, I discussed that below. @username_0: Please see the discussion which I believe is clarifying.  

---

## 1 answers

### Answer by username_2 on 2010-09-27. Score: 5 | Accepted answer

First note that #2 and #3 are saying the same thing. Next, notice that if `u` is an ancestor of `v` in `T`, then in a pre-order traversal, we see `u` before `v`, and therefore `pre(u) < pre(v)`. On the other hand, since `T` is a depth-first search tree (as opposed to an arbitrary tree) of the connected undirected graph `G`, and $(u,v) \in G-T$, we can deduce that `pre(u) results in u being an ancestor of v.`

The following image, taken from Wikipedia, can help:

![](https://upload.wikimedia.org/wikipedia/commons/thumb/6/67/Sorted_binary_tree.svg/500px-Sorted_binary_tree.svg.png)

Preorder traversal sequence: F, B, A, D, C, E, G, I, H (root, left, right)

Postorder traversal sequence: A, C, E, D, B, H, I, G, F (left, right, root)

> **Comments:**
> **username_0**: Yeah, was able to figure out the first part on my own. The problem with the second part is that I don't see how it would be *necessary* that $u$ be an ancestor of $v$. Doesn't my counter-example for #2 show that that statement isn't necessarily true for the conditions they've supplied?  
> **username_0**: Regarding the image you've attached - take vertices $A$ and $D$. $pre(A) < pre(D)$, but $A$ is not an ancestor of $D$.  
> **username_2**: Have you noticed the sentence `Let (u,v) be an edge in G that is not in T` at the beginning of the question?  
> **username_0**: Yes, but I'm not clear on how it impacts the question other than specifying that $u$ and $v$ aren't adjacent. Is that the key to this? Can you elaborate a bit more?  
> **username_2**: @username_0: I'm very sorry if my explanation isn't clear. Yet I don't know how to clarify it more, since it seems obvious to me. Fortunately, there's a workaround (an intuition, not a proof): Try drawing a graph G as described by the problem, such that in its depth-first tree `T`, we have $(u,v) \in G-T$ and  `pre(u)<pre(v)`, but it violates the `u is v's ancestor` condition. If you succeed, send the link to the graph's image, and then I will know where the problem lies. Otherwise, you'll get a clear intuition as why it is correct.  
> **username_0**: @Sadeq: In the image you posted, consider vertices $A$ and $D$. These satisfy the conditions that $pre(A) < pre(D)$ and $A$ is not an ancestor of $D$. Define the graph $G$ as $T$ with the additional edge $(u,v)$. Now $(u,v)\in G-T$, and we have constructed a valid counter-example. I am very interested in understanding what is wrong with this counter-example, so please tell me where the hole is.  
> **username_0**: @Sadeq: Please see my updated question description for details. Thank you for your help so far!  
> **username_2**: @username_0: The DFS of the graph you depicted is: F-B-A-D-C-E-G-I-H. Then, the edge (A,D) is in T, and the premise of the problem is NOT satisfied. I advise you to review DFS: http://en.wikipedia.org/wiki/Depth-first_search  
> **username_0**: @Sadeq: Ok, I was confused about the depth-first search part. I hadn't heard of the concept of applying a depth-first search to a general graph to generate a tree. Thank you again for your help.  
> **username_2**: @username_0: I'm very happy I was able to help.  

---

