A graph G has m vertices of odd degree and n | vedclass

Name: Exam Paper Generator | JEE NEET Paper Generator | Vedclass
Brand: Vedclass
Rating: 5 (35 reviews)

Question

(B) According to the Handshaking Lemma,the sum of the degrees of all vertices in a graph is equal to twice the number of edges,which is an even number

Vedclass · Accepted Answer

$m$ is an even number

Vedclass · Answer

(B) According to the Handshaking Lemma,the sum of the degrees of all vertices in a graph is equal to twice the number of edges,which is an even number.Let $V_{odd}$ be the set of vertices with odd degree and $V_{even}$ be the set of vertices with even degree.The sum of degrees is $\sum_{v \in V_{odd}} 	ext{deg}(v) + \sum_{v \in V_{even}} 	ext{deg}(v) = 2|E|$.Since $\sum_{v \in V_{even}} 	ext{deg}(v)$ is always even,the sum $\sum_{v \in V_{odd}} 	ext{deg}(v)$ must also be even for the total sum to be even.For the sum of $m$ odd numbers to be even,$m$ must be an even number.Therefore,the number of vertices of odd degree,$m$,is always even.

$A$ graph $G$ has $m$ vertices of odd degree and $n$ vertices of even degree. Then which of the following statements is necessarily true?

Similar Questions

List all the subsets of the set $\{-1, 0, 1\}$.

For any sets $A$ and $B$,show that $P(A \cap B) = P(A) \cap P(B).$

Let $A = \{1, 2, \{3, 4\}, 5\}$. Which of the following statements is incorrect and why?
$\{\varnothing\} \subset A$

If $A$ and $B$ are two sets,then $A \cup B = A \cap B$ if and only if

Write the set builder form of the set $ A = \{-1, 1\} $.

Vedclass Test Series

Exam Paper Generator

Online Exam Module