T is a tree and V is a vertex of T of maximum degree in T,
say the degree of V in n. Prove that T has atleast n
vertices of degree 1.
- 1 Answers
- 1974 Views
- TCS, I also Faced
- E-Mail Answers
Answer Posted / Saurabh Gangwar
To prove this, we can use the Handshaking Lemma which states that the sum of the degrees of all vertices in a graph equals twice the number of edges. Since the maximum degree vertex V has degree n, there are n edges incident on V. Each of these edges connects V to another vertex. Therefore, T must have at least n - 1 other vertices (since V is one). However, since each of these n - 1 vertices can have a degree 1 edge connected to V, we also have at least n - 1 vertices of degree 1. But remember that our initial vertex V could also have a degree 1 edge incident on it if T has more than n vertices (if the sum of degrees equals twice the number of edges and the maximum degree is less than the total degrees divided by 2). So, we can conclude that T has at least n vertices of degree 1.
| Is This Answer Correct ? | 0 Yes | 0 No |
Post New Answer View All Answers
Can anyone send me iocl written test paper fro computer engineers
what is the different between view and materialized view in oracle DBA?
if u have question papers/sample papers of any of PSUs,plz send me at dinesh.pandey3@gmail.com
Write a function that responds to a click anywhere on the page by displaying an alert dialog. Display the event name if the user held Shift during the mouse click. Display the element name that triggered the event if the user held Ctrl during the mouse click.
BEL old probationary engineering questions and answers
hai iam selected in po exam in allahabad bank . my interview date is 02-06-2009. so plese send me some sample question on my email. my email is nitinbikhani@yahoo.com
who is your favourate actor in tollywood tellme about him in few points
anyone send me aptitude and technical placement paper of Hewitt
please provide me the type of questions or question pattern of bally.
Please send me Sample papers National Informatics Centre (NIC) Programmer. I am giving this paper first time..so if any one have previous question papers send to manoj200.yadav@gmail.com. thnx in advance
sir ,,kindly provide me 10 year old solved question papers of gate ,i am from CS. branch...
sir,i am a 3rd yr student of computer engineering. i need atleast 10 previous year's placement papers of hcl,infosys & wipro. please send me these papers as early as possible.thanx for giving me your precious time.
i need the placement paper of ford IT service...
If i update, insert or delete records in my view will it affect my base table?????
what are the main points to be included in our introduction when asked in hr...??
