Several proofs related to the definitions of trees and forests

Question

Below I have a few proofs that I'd like to get checked. Thanks.

---

a. Prove every tree with $v$ vertices has exactly $v - 1$ edges

Solution:

We want to show that $v - e = 1.$ We use the process of tree pruning(removing a vertex of degree $1$ from the tree along with the edge that occurs at that vertex). This process is well-defined because removing a vertex and an edge still leaves us with a tree since trees contain no cycles and removing edge/vertex pair doesn't add any cycle to the tree.

Every tree with more than one vertex can be pruned because every tree with two or more vertices has at least two vertices of degree $1.$ (Consider a longest simple path $P$ in the tree whose length is $x.$ The degree of its endpoints is at most $x.$ Otherwise $P$ is no longer the longest simple path).

The difference $v - e$ stays constant throughout the pruning process. At some point the tree will be reduced down to a single vertex so that $v - e$ is $1.$ Since the the difference $v - e$ stays constant all through the pruning, we can say that $v - e = 1$ for a tree.

b. In a forest with $v$ vertices and $k$ components, the number of edges is $v - k.$

Solution:

By (a) above, $v - e = 1$ for each component tree meaning $v - e$ is constant in every component. Since there are $k$ components $v - e = k$ and so the number of edges is $v - k.$

c. Suppose that a graph has $20$ vertices, $15$ edges, and contains no cycles. Then how many components does the graph contain?

Solution:

This graph has no cycles so it must be a tree, but a tree must contain exactly $v - 1$ edges if $v$ is the number of vertices. Thus we are dealing with a forest. By (b) above, the number of components is $20 - 15 = 5.$

d. Suppose that a graph contains an equal number of vertices and edges. Show that the graph must contain at least one cycle

Solution:

A graph with equal number of vertices and edges is not a tree by (a) above, but perhaps a forest. Then this forest has $0$ components meaning this graph is not a forest either. Thus this graph must contain at least one cycle.

Answer 1

If I'm not mistaken, your ideas are correct, although your wording feels a little bit clumsy at times. I'll point out only the flaws in your logic; I encourage you to go over your wording yourself.

a. [...] (Consider a longest simple path $P$ in the tree whose length is $x$. The degree of its endpoints is at most $x$. Otherwise $P$ is no longer the longest simple path). [...]

I don't understand how this proves the fact that any tree with more than one vertex has at least two vertices of degree 1. Are you saying that the longest simple path has length 1?

c. This graph has no cycles so it must be a tree [...]

This is not correct. Don't say thing that aren't correct.

d. [...] Then this forest has 0 components meaning this graph is not a forest either. [...]

I'm not sure which definition you learned, but it seems to me that the empty graph ($V = E = \varnothing$) is a graph with the same number of vertices and edges. It is the unique graph with $0$ components, and it is trivially a forest. Contrary to what the question would have you believe, it doesn't contain a cycle.

I'm guessing that the vertex set in your definition of graphs is assumed to be non-empty. In that case, the phrase "this graph is not a forest" is inadequate. A better way to put it: "this is not a graph at all". (After all, once we acknowledge that it is a graph, it is most definitely a forest.) Admittedly I'm nitpicking here, but it is my opinion that corner cases do matter!