Graph Theory Inductive proof

Question

This is just a simple Proof by induction that I hoped one of you could check.

Definition A graph is called a tree if it is a connected graph which contains no cycles.

Theorem Let G be a tree. Then

$$|V(G)| = |E(G)| + 1.$$

Proof Consider the 'base case' where $|V(G)| = 2$. Then clearly $|E(G)| = 1$. We make the assumption that if $|V(G)| = n - 1$ then $|E(G)| = n - 2$ and proceed to add a vertex to the graph. If the tree structure is to be preserved then only one edge can join this vertex to the graph. Hence, $|V(G)| = n$ implies that $|E(G)| = n-1$. More concisely,

$$|V(G)| = |E(G)| + 1$$

as expected.

Thanks!

Answer 1

Assuming the graph is bidirectional (otherwise a tree in the common sense is not connected if hierarchical)

When you say there is a unique path and the graph is connected and acyclic, you are basically saying [1]:

\foreach(v1, v2) | v1 != v2 -> \exists ! p | v1->p->v2

Let's call our new node x . It must be connected to the rest of the graph, so it needs to be connected to at least one vertex. Let's say it's directly connected to v2:

v2 -> x && x -> v2

then we get, by lemma 1

\exists ! p1 | v1 -> p1 -> v2 -> x

If x was directly connected to any other vertex v3, then you would have:

(\exists ! p2 | v1 -> p2 -> v3 -> x && p2 != p1) =>  p1->v2 != p2->v3

which leads to a contradiction because now we have two different paths from v1 to x, respectively p1->v2 and p2->v3 .

Therefore x must be connected by at least 1 edge (per connected definition) and at most 1 edge (otherwise contradiction). Therefore exactly one edge.