# Undirected graph whose BFS and DFS trees have roots of degree 2

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?

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

## 1 Answer

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.