The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+12 votes
2.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 (363k points)
edited by | 2.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.4k 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 (7.1k points)
Answer:

Related questions



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

42,599 questions
48,601 answers
155,674 comments
63,743 users