Graph G=(N,E)
N={a,b,c,d,e,f}
E={(a,f),(d,b),(a,c),(d,e),(e,c),(f,d),(b,f)}
Give a subgraph of G that is a tree of depth 4 and which has 2 nodes at level 3.
Basically, I'm not looking for the answer, I'm just curious as to whether this is actually possible. Drawing out the graph and looking at it is telling me that there is no possible solution.
D is the only node that connects to two nodes, which means that it must be level 2 with B and E on level 3. However, if E is level 3 (depth 2), it means that C must be depth 3 - and since the depth must be 4 it means it is not solvable.
Am I missing something here?
If you interpret the graph as a directed graph (and want the subtree to have all edges point away from the root) then we run into the problem you describe. (Also, the problem that there's no directed path between $a$ and $b$ in either direction.)
So I'm forced to conclude that the graph is meant to be undirected: the order in which the endpoints of an edge are listed has no meaning, and $(d,b)$ could have just as easily been $(b,d)$.
In that case, for there to be two vertices at level $3$ (and one vertex at levels $1, 2, 4, 5$) means that the vertex at level $2$ must have three neighbors: one parent, and two children, and as before, this means that the vertex at level $2$ is either $d$ or $f$ (the second case is symmetric). But you no longer run into the problem you describe if you delete edges judiciously.