Exams › GATE › Technical

Which of the following statements 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

Correct answer: Both P and Q

Solution

In undirected graphs, the sum of the degrees of all vertices is always even because each edge contributes two to the total degree count. Additionally, the number of vertices with odd degrees must be even due to the Handshaking Lemma, which states that the sum of the degrees of all vertices is equal to twice the number of edges.

Related GATE Technical questions

• The truth table X Y f(X,Y) 0 0 0 0 1 0 1 0 1 1 1 1 represents the Boolean function
• The decimal value 0.5 in IEEE single precision floating point representation has
• A process executes the code fork(); fork(); fork(); The total number of child processes created is
• The protocol data unit (PDU) for the application layer in the Internet stack is
• Which of the following problems are decidable? 1) Does a given program ever produce an output? 2) If L is a context-free language, then is L̄ also context-free? 3) If L is a regular language, then is L̄ also regular? 4) If L is a recursive language, then is L̄ also recursive?
• A binary operation ⊕ on a set of integers is defined as x ⊕ y = x² × y². Which one of the following statements is TRUE about ⊕?

⚔️ Practice GATE Technical free + battle 1v1 →