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

Let $A = \{a, e, i, o, u\}$ and $B = \{a, b, c, d\}$. Is $A$ a subset of $B$? No. (Why?). Is $B$ a subset of $A$? No. (Why?)

Consider the sets $\phi, A=\{1,3\}, B=\{1,5,9\}, C=\{1,3,5,7,9\}$. Insert the symbol $\subset$ or $\not\subset$ between the pair of sets: $A, \ldots B$.

Which of the following is an empty set?

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

Write the following set in the set-builder form: $\{ 5, 25, 125, 625 \}$

Vedclass Test Series

Exam Paper Generator

Online Exam Module