# 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