Equivalent tree definitions

Lemma

The following conditions are equivalent for a graph .

1. is a tree.
2. is path connected and .
3. has no cycles and .

Proof

Proof of .

We prove this by induction on the number of vertices.

Suppose and set then if had an edge it must be . However, we then have a cycle so it would not be a tree. So .

Suppose the induction hypothesis is correct on all graphs with and let be a graph with .

As a finite tree that has more than one vertex must have at least two leaf vertices let be such a leaf vertex with single edge . Remove to form . Note that has to be a tree as if a cycle existed in it would exist in and as was connected so is as no path would need to use .

By the induction hypothesis . Giving Thus proving our statement by induction.

Proof of .

Suppose we have a graph that is connected and . Though has a cycle in it.

Take a minimal, in terms of , counter example.

Note that from problem 3(a) we have that says one vertex in must have (it has to be at least 1 as it is connected).

As can’t be in the cycle (this would require degree 2), it must be outside. We can now remove this vertex and the remaining graph will still satisfy with the same cycle. The new graph will be a smaller example and contradict its minimality.

This proves the claim.

Proof of .

Note all we need to show is that is connected.

Lets use proof be contradiction. Suppose satisfies but is not a tree, let be a minimal such example.

If has a vertex of degree 1, we can remove it and find a smaller counter example. Therefore must not have any vertices of degree 1.

Take a connected component of , as it has no vertices of degree 1 they must have vertices of degree or more. Repeat the argument in a finite tree that has more than one vertex must have at least two leaf vertices, this shows that this connected component has a cycle it in. This contradicts so no such graph exists.

This proves this claim and the equivalence.