The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+16 votes

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 (396k points)
edited by | 2.5k views
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

+26 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.5k points)
edited by
+8 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 Boss (11k points)

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
50,129 questions
53,252 answers
70,506 users