The number of vertices of odd degree in any graph of 'n' vertices with 'e' edges is :
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: B. even
Explanation
By the handshaking lemma, the sum of the degrees of all vertices in a graph equals 2e, which is always an even number. If the count of odd-degree vertices were itself odd, the sum of their degrees would be odd, and adding the even sum contributed by the even-degree vertices would make the overall total odd, contradicting the handshaking lemma. Therefore the number of vertices of odd degree in any graph must always be even.More Discrete Structures and Optimisation questions
- Let R = {(1, 2), (3, 4), (2, 2)} and S = {(4, 2), (2, 5), (3, 1), (1, 3)} be two relations. The composite relation R∘S of R and S is :
- Out of 32 people, 30 save paper and 14 people save plastic bottles. What is the total number of people who save both paper and plastic bott…
- Consider a linear program {max cᵀx | Ax ≤ b}. Which of the following statements is true?
- In a pack of 42 cards, 3 cards are chosen one after the other. Find the number of ways this can be done without replacement:
- A positive integer is selected at random from the set of positive integers not exceeding 200. What is the probability that the selected num…
- Match List I with List IIList I List II A. If the Indian team wins, then it is raining I. Inverse B. If the Indian team does not win, then…