Prove or disprove: for all graphs $G = (V, E)$, if $|E| = |V| - 1$ then $G$ is a tree.

111 Views Asked by At

Relevant Fact We know that for all graphs $G = (V, E)$, if $G$ is a tree then $|E| = |V| - 1$.

Definitions A tree is a graph that is connected and has no cycles. A cycle is like a path, except it starts and ends at the same vertex.

Will soon update with what I have so far. For time being, feel free to add anything.

Would mention that this question is unique in that it does not assume the graph is connected. Thanks everyone!