We know that every graph is isomorphic to a subgraph of a complete graph. Similarly, can we say that every graph is isomorphic to a quotient graph of a tree?



Quotient graph of a tree
Yes, if $G$ is connected (and non-empty for simplicity).


Choose a vertex $v\in V(G)$. We define a tree $T$ in which the vertices are all the paths in $G$ that start in $v$ (including the path of length zero that only contains $v$). Two paths $P$ and $Q$ (as vertices in $T$) are connected by an edge in $T$ if their lengths differ by one, and one is contained in the other one. Draw this for some small graphs to see that this construction is related to the idea of "universal cover" in topology.


Now, we construct a quotient of $T$ that is isomorphic to $G$. For that, identify two vertices in $T$ (that is, paths in $G$) if they have the same end-vertices in $G$. The isomorphism between $G$ and this quotient maps a vertex $w\in V(G)$ to the equivalence class of paths between $v$ and $w$ (here we need the connectivity of $G$).


