I wanted to prove the claim "A graph is a tree if and only if it has one fewer edge than it has vertices." Is this true or false, and why?

551 Views Asked by At

For this question I chose 4 as the answer however it was wrong. Can someone please explain the right answer This were the choices:

Suppose I wanted to prove the claim "A graph is a tree if and only if it has one fewer edge than it has vertices." Is this true or false, and why?

  1. This is true, because it is a known fact that the number of edges in a tree is one less than the number of vertices.

  2. This is false, because one can construct a disconnected graph with five vertices and four edges that is not a tree.

  3. This is false, because trees do not always have a number of edges equal to the number of vertices minus one.

  4. This is true, because the number of edges in a tree is always one less than the number of vertices, and also, you can't construct a graph that is not a tree if the number of edges is one less than the number of vertices. So both directions of the iff are satisfied.

1

There are 1 best solutions below

4
On

Consider a cycle on 3 vertices $A,B,C$ and a stand-alone vertex $D$. You have 4 vertices, 3 edges and clearly not a tree.

But if you additionally assume $G$ is simple and connected, the claim is true.