Answer to Question #184200 in Discrete Mathematics for farhana

Question

 Suppose you have a graph with v vertices and e edges that satisfies v=e+1. Must the graph be a tree? Prove your answer.

Answer 1

A graph with v vertices and e edges that satisfies v=e+1, is not necessary a tree.

For example, the graph which is a triangle (complete 3-graph) and an isolated vertex.

This graph contains v=4 vertices, and e=3 edges, that satisfy v=e+1. But this graph is disconnected and it has a 3-cycle and an isolated vertex. A tree is a connected graph without cycles. Therefore, the given graph is not a tree.