edited by
15,916 views
25 votes
25 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
edited by

2 Answers

Best answer
44 votes
44 votes
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
edited by
8 votes
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

Answer:

Related questions

1 votes
1 votes
1 answer
1
gatecse asked Dec 9, 2020
402 views
In an undirected graph, if we add the degrees of all vertices, it is:oddevencannot be determinedalways $n+1,$ where $n$ is number of nodes
16 votes
16 votes
2 answers
2
go_editor asked May 27, 2016
2,165 views
An undirected graph has $10$ vertices labelled $1, 2,\dots , 10$ and $37$ edges. Vertices $1, 3, 5, 7, 9$ have degree $8$ and vertices $2, 4, 6, 8$ have degree $7.$ What ...
44 votes
44 votes
9 answers
4
Madhav asked Feb 14, 2017
17,292 views
$G$ is an undirected graph with $n$ vertices and $25$ edges such that each vertex of $G$ has degree at least $3$. Then the maximum possible value of $n$ is _________ .