Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Draw a graph on $5$ vertices that satisfies all of the following conditions:
- $G$ is an undirected connected graph.
- For every node $v∈V$, in the spanning tree received by BFS($v$), $\deg v=2$.
- 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?
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.
