Proving that an acyclic graph with $n$ vertices has $\leq n-1$ edges

Question

By the handshake rule, $∑\deg(v) = 2|E|$. Each tree in a forest has at least one leaf node (a vertex with degree $1$). Therefore, the sum of the degrees of all vertices in the graph is at most:

$$∑\deg(v) ≤ (|V| - 1) + |V| - 1$$

The first term, $|V| - 1$, comes from the fact that each tree in the forest has $|V| - 1$ edges, and there are at most $|V| - 1$ trees in the forest. The second term, $|V| - 1$, comes from the fact that the root node of each tree has degree at most $|V| - 1$. Thus,

$$∑\deg(v) ≤ 2|V| - 2$$

Using the handshake rule:

$$∑\deg(v) = 2|E|$$

Combining the equation:

$$2|E| ≤ 2|V| - 2$$

Dividing both sides by $2$, we get:

$$|E| ≤ |V| - 1$$

Does my proof work here that the number of edges is less than or equal to the number of vertices minus $1$.

Answer 1

When proving a "basic" statement like this, you should be extra careful about stating your assumptions. After all your whole theorem is a common "basic assumption", so if you aren't careful you can easily end up assuming some other well-known claims that easily imply your theorem, instead of producing a complete proof yourself.

Here are some specific things I think you should be more careful about:

1. What is a "tree"? I'm guessing you're defining a tree to be an undirected, connected, acyclic graph.
2. How do you know each tree has $|V| - 1$ edges? (In fact, this is not true: by default $V$ and $E$ are referencing your full graph, and each connected component of the graph may have some smaller number of edges.)
3. Anyway, if we do know that each tree has (num vertices in tree) -1 edges, then that wouldn't produce $|V|-1$ edges total. Instead it would produce $|V| - \text{(num connected components})$ edges total.
4. Overall, your proof of the equation $\sum \deg(v) \le (|V|-1) + |V|-1$ is either missing several steps or needs a whole different approach - it's hard to tell which without better explanation from you.

The good news: Starting from that statement about $\sum \deg(v)$, the last several steps of your proof are valid and well explained. The mistakes in the initial steps make the proof incomplete though.