Graph the number of vertices of odd degree

Q.  In a graph the number of vertices of odd degree is always
- Published on 23 Jun 15

a. even
b. odd
c. sometimes odd sometimes even
d. None of the above.

ANSWER: even

Related Content

 

    Discussion

  • Nirja Shah   -Posted on 25 Nov 15
    - This is solved by using the Handshaking lemma

    - The partitioning of the vertices are done into those of even degree and those of odd degree

    - The formula is as follows:

    - ∑(v∈V) deg (v) = 2 | E |

    - By the Handshaking Lemma, the value of the lefthand side of the equation equals twice the num­ber of edges, and so it is even.

    - The first summand on the righthand side is even since it is a sum of even values.

    - Hence, the second summand on the righthand side must also be even.

    - But since it is entirely a sum of odd values, it must must contain an even number of terms.

    - That is, there must be an even number of vertices with odd degree.

➨ Post your comment / Share knowledge


Enter the code shown above:

(Note: If you cannot read the numbers in the above image, reload the page to generate a new one.)
▲