The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+12 votes
2k views

Which of the following statements is/are TRUE for undirected graphs?

P: Number of odd degree vertices is even.
Q: Sum of degrees of all vertices is even.

  1.  P only
  2.  Q only
  3.  Both P and Q
  4.  Neither P nor Q
asked in Graph Theory by Veteran (357k points)
edited by | 2k views
+1
The No. of odd degree vertices in any graph is always even.

In any graph sum of degrees of vertices is twice the no of edges.

So, Both are True.

2 Answers

+25 votes
Best answer
Both are correct

P: sum of odd degree $+$ sum of even degree$=2\times \text{no. of edges}$

sum of odd degree$=2\times \text{no. of edges - sum of even degree}$

The right hand side must be even as the difference of $2$ even numbers is always even.

Q: each edge is counted twice so sum of degree is always even
answered by Boss (14.3k points)
edited by
+7 votes

A and C are odd degree of vertices so number of odd degree vertices = 2 so P is True and sum = 3 + 2 +3 +2 = 10 which is even 

so P and Q are both true option C

answered by Loyal (6.7k points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

39,848 questions
46,815 answers
141,154 comments
59,066 users