## Equivalent definition of tree

Prove that a graph $$G$$ is a tree if and only if $$G$$ has no cycle and $$| E (G) | = | V (G) | -1$$ .

Prove the statement without using the theorem on equivalent tree definitions, or if you need any implication from this theorem, then reproduce it in its entirety.

• #### Solution

Consider the definition of a tree, for example, that it is a connected graph without cycles.

The property without cycles is preserved on both sides.

Forward implication (connected and without cycles implies $$| E (G) | = | V (G) | -1$$):

By induction according to $$| V_G |$$, connected without cycles has a leaf $$u$$, for $$G-u$$ the given equation applies, which with the addition of $$u$$ does not violate.

Backward implication ($$| E (G) | = | V (G) | -1$$ and without cycles implies connectedness):

For contradiction, suppose that $$G$$ is disconnected without cycles with the components $$C_1,…, C_k$$. The components are connected without cycles, so they fulfill the previous implication. Then $$| E (G) | = | E (C_1) | +… + | E (C_k) | = | V (C_1) | -1 +… + | V (C_k) | -1 = | V (G) | -k$$, a contradiction.