Discrete Math - The MKD Remix

A graph \(G\) is a tree if and only for every pair of vertices of \(G\) there is exactly one trail between the vertices.

First, we’ll assume that \(G\) is a tree and prove by contradiction that for any pair of vertices of \(G\) there is exactly one trail between the vertices. Suppose that \(G\) is a tree, then \(G\) is connected so for every pair of vertices there is a least one trail joining the vertices. Now suppose that for some pair of vertices \(u\) and \(v\) there are two (or more) trails between \(u\) and \(v\) - then we can go from \(u\) to \(v\) along one trail and go back to \(u\) along another trail; this means that there is a cycle in \(G,\) but since \(G\) is a tree, it has no cycles. We have gotten a contradiction, so there can be no pair of vertices that are joined by two (or more) trails so there is exactly one path joining any pair of vertices of the tree.

Secondly, we’ll assume that for every pair of vertices of \(G\) there is exactly one trail between the vertices and prove by contradiction that \(G\) must be a tree. Notice that \(G\) is connected since for any pair of vertices there is (exactly) one trail that joins them. If \(G\) has no cycles then it is a tree, so in order to get a contradiction we assume that \(G\) does have a cycle \(v_{0}v_{1} \cdots v_{n-1}v_{n}\) where \(v_{0} = v_{n}\) but all the other vertices are not repeated in the cycle. Choose a value of \(k\) so that \(0 < k < n\) to create two different trails \(v_{0} \cdots v_{k}\) and \(v_{k} \cdots v_{n}.\) After reversing the order of vertices in the second trail, we now have two different trail between the vertices \(v_{0}\) and \(v_{k}\) which contradicts the assumption that for every pair of vertices of \(G\) there is exactly one trail between the vertices. This proves that \(G\) cannot have a cycle, and since we already proved that \(G\) is connected, we can conclude that \(G\) is a tree.

Q.E.D.

For every positive integer \(n,\) if a tree has \(n\) vertices then the tree has \(n-1\) edges.

We use mathematical induction on the number of vertices \(n.\)

Let \(P(n)\) be the predicate "If a tree has \(n\) vertices then the tree has \(n-1\) edges." We will prove that \((\forall n \in \mathbb{N}_{>0})P(n)\) is True.

Basis Step: \(P(1)\) is True since a tree that has \(1\) vertex has \(0\) edges (otherwise, the edge would have to be a loop, but trees are simple graphs that don’t have loops.)
We can also prove that \(P(2)\) is True in case the proof of \(P(1)\) feels unsatisfying. If a tree has \(2\) vertices, then there is \(1\) edge between those two vertices; since a tree is a simple graph, it cannot have either loops or parallel edges, so the tree mus have exactly \(1\) edge. This proves that \(P(2)\) is True.

Induction Step: First, we assume that the induction hypothesis \(P(k)\) is True for some positive natural number \(k\).

Secondly, we will prove that the conditional \(P(k) \rightarrow P(k+1)\) must be True, which means we can use modus ponens (or the equivalent tautology \(( P(k) \land ( P(k) \rightarrow P(k+1) ) ) \rightarrow P(k+1)\)) to show that \(P(k+1)\) is also True.

Assume that \(P(k)\) is True for the positive integer \(k,\) that is, if a tree has \(k\) vertices then the tree has \(k-1\) edges. We can assume \(k \geq 2\) since the cases when \(k \in \{ 1, 2 \}\) were proved in the Basis Step. Suppose that we have a tree \(T\) that has \(k+1\) vertices; we will prove that the tree must have \(k\) edges. Let \(v\) be a vertex of \(T\) such that the degree of \(v\) is \(1\) - such a vertex must exist because the tree \(T\) has no cycles. Remove \(v\) and the edge that has \(v\) as an endpoint to obtain the subgraph \(T-v,\) and notice that for every pair of vertices of \(T-v\) there is exactly one trail between the vertices. Using the previous theorem, \(T-v\) is a tree with \(k\) vertices, and the induction hypothesis allows us to conclude that \(T-v\) has \(k-1\) edges. We now reinsert vertex \(v\) and the edge that was removed to obtain a tree that has \(k+1\) vertices and \(k\) edges. Therefore, \(P(k+1)\) is True, too. This proves that \(P(k) \rightarrow P(k+1)\).

Conclusion Step: We have proven both the Basis Step and the Induction Step. Therefore, we can use universal generalization to conclude that for all positive integers \(n,\) if a tree has \(n\) vertices then the tree has \(n-1\) edges.

Q.E.D.