Let $G=(V,E)$ be a simple undirected graph with $|V|=4$. Some run of DFS produces a spanning tree in which the root has degree 2. Claim: $|E|\leq 4$.
Basically I know it's true but I have no idea how to formalize it. Is there someone here who can give me a formal solution ?