Solution to Suppose you have a graph with v vertices and e edges that satisfies v=e+1. Must … - Sikademy
Author Image

Archangel Macsika

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.

The Answer to the Question
is below this banner.

Can't find a solution anywhere?

NEED A FAST ANSWER TO ANY QUESTION OR ASSIGNMENT?

Get the Answers Now!

You will get a detailed answer to your question or assignment in the shortest time possible.

Here's the Solution to this Question

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.


Related Answers

Was this answer helpful?

Join our Community to stay in the know

Get updates for similar and other helpful Answers

Question ID: mtid-5-stid-8-sqid-3118-qpid-1817