0
$\begingroup$

Draw a graph on $5$ vertices that satisfies all of the following conditions:

  1. $G$ is an undirected connected graph.
  2. For every node $v∈V$, in the spanning tree received by BFS($v$), $\deg v=2$.
  3. For every node $v∈V$, in the spanning tree received by DFS($v$), $\deg v=2$.

I was trying to draw many graphs but none of them satisfied all of the conditions.

I was also trying to disprove that such a graph exists, but couldn't find any strong claim that I could use for my proof.

Can you give me a hint?

$\endgroup$
1
  • 1
    $\begingroup$ Try to prove that there exists a unique graph satisfying conditions 1 and 2. This graph doesn't satisfy condition 3. $\endgroup$ – user114966 Nov 20 '20 at 10:42
0
$\begingroup$

The degree of the root in a BFS tree equals the degree of the vertex in the original graph. Hence condition 2 states that your graph is 2-regular. Since it is connected, it must be a 5-cycle. Running DFS on the 5-cycle results in a path, and in particular, the root has degree 1.

This argument shows that there's nothing special about the number 5: the result remains true for any number of vertices.

$\endgroup$

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.