- Thread starter
- #1

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?

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.

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: