Yahoo Answers is shutting down on May 4th, 2021 (Eastern Time) and beginning April 20th, 2021 (Eastern Time) the Yahoo Answers website will be in read-only mode. There will be no changes to other Yahoo properties or services, or your Yahoo account. You can find more information about the Yahoo Answers shutdown and how to download your data on this help page.
Trending News
Help with the proof?
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?.
Sorry, got it backwards: the minimum number of edges to connect n vertices is n-1.
This is for discrete math in the section about graphs and vertices.
5 Answers
- Anonymous2 decades agoFavorite 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.
- 2 decades ago
Choose a vertex. This has to be connected to the remaining N-1 vertices, so you need N-1 edges.
- Anonymous2 decades ago
n=3 , n-1= 3-1=2, or 2 edges
- 2 decades ago
Where did you get that theorem?
A triangle has 3 edges, and 3 vertices.
n-1 = 2.
- How do you think about the answers? You can sign in to vote the answer.
- a_ebnlhaithamLv 62 decades ago
Consequently -.-.-.-.-.-.-.-.- The no. of vertices (.) is less than the no. of edged (-) by 1
