1
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ But then that graph would not be a tree since not all vertices are connected? $\endgroup$ – Ema Li Sep 16 '18 at 1:21
  • $\begingroup$ What is your definition of tree? The graph in @gt6989's claim is not a tree, but that's the whole point. You claimed it had to be a tree, and he showed that it did not have to be a tree. $\endgroup$ – The Count Sep 16 '18 at 1:22
  • $\begingroup$ Oh man the answer is 2!!! I misinterpreted the question... Thanks! $\endgroup$ – Ema Li Sep 16 '18 at 1:25
  • $\begingroup$ @DenadaBakiasi exactly $\endgroup$ – gt6989b Sep 16 '18 at 1:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.