Equivalent definition of tree
Task number: 4212
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.
