Help with the proof?

Question

I need help in proving the following theorem: 

The minimum number of vertices to connect n edges is n-1.

Now I know that if you have one vertex then that is called an isolated vertex and therefore has no edges, which holds true for the theorem (since 1-1 = 0). However, I don't know how to prove the rest of the theorem. Say I have 3 vertices. How do I prove that there are at least two edges?.

Anonymous · Accepted Answer

The key word is "connect." They don't have to loop back on themselves to make a closed figure. You need two vertices to make an edge, and for each successive edge you need one more vertex to connect onto either vertex you already have.

Okay, that's not exactly a PROOF per se but you get the idea.

snpr1995 · Answer

Choose a vertex. This has to be connected to the remaining N-1 vertices, so you need N-1 edges.

Anonymous · Answer

n=3 , n-1= 3-1=2,  or 2 edges

Ernest Maxwell · Answer

Where did you get that theorem?

A triangle has 3 edges, and 3 vertices.

n-1 = 2.

a_ebnlhaitham · Answer

Consequently -.-.-.-.-.-.-.-.- The no. of vertices (.) is less than the no. of edged (-) by 1

Help with the proof?

Trending Questions