# Graph theory proof related to trees

#### Yuuki

##### Member
Prove that a graph on v vertices that has no cycle is connected iff it has precisely v-1 edges.

Necessary Condition:
A connected graph with no cycles is a tree. Therefore, it has v-1 edges.

Sufficient Condition:
I need help with this.
How can I use "a connected graph has no cycles iff it has exactly v-1 edges"?

Also, is my proof for the necessary condition correct?

edit:
I was able to come up with one.

Suppose G is disconnected.
Let the components be G1 and G2, each having n and m vertices respectively.
Since both are connected and have no cycles, they have n-1 edges and m-1 edges.
Hence, G has only (n-1)+(m-1)=v-2 edges.
Therefore, if G has v-1 edges and has no cycles, G must be connected.

Last edited:

#### Sudharaka

##### Well-known member
MHB Math Helper
Prove that a graph on v vertices that has no cycle is connected iff it has precisely v-1 edges.

Necessary Condition:
A connected graph with no cycles is a tree. Therefore, it has v-1 edges.

Sufficient Condition:
I need help with this.
How can I use "a connected graph has no cycles iff it has exactly v-1 edges"?

Also, is my proof for the necessary condition correct?

edit:
I was able to come up with one.

Suppose G is disconnected.
Let the components be G1 and G2, each having n and m vertices respectively.
Since both are connected and have no cycles, they have n-1 edges and m-1 edges.
Hence, G has only (n-1)+(m-1)=v-2 edges.
Therefore, if G has v-1 edges and has no cycles, G must be connected.
Hi Yuuki,

I think you'll have to revise what is meant by Necessity and Sufficiency in mathematics. In you problem you have to show that,

"A graph with $$v$$ vertices that has no cycles is connected iff it has precisely $$v-1$$ edges"

Here the condition, "a connected graph with $$v$$ vertices and no cycles" is sufficient for that graph to have $$v-1$$ edges. You have proved this using the definition of Trees.

On the other hand "a connected graph with $$v$$ vertices and no cycles" is also necessary for that graph to have $$v-1$$ edges. Hence we use the phrase, "necessary and sufficient" for "iff" statements. For this you may assume that, "$$G$$ is a disconnected graph with no cycles which has $$v$$ vertices and $$v-1$$ edges". This will give you a contradiction.