Exams › GATE › Technical

An ordered n-tuple (d₁, d₂,..., dₙ) with d₁ ≥ d₂ ≥... ≥ dₙ is called graphic if there exists a simple undirected graph with n vertices having degrees d₁, d₂,..., dₙ respectively. Which of the following 6-tuples is NOT graphic?

1. (1, 1, 1, 1, 1, 1)
2. (2, 2, 2, 2, 2, 2)
3. (3, 3, 3, 1, 0, 0)
4. (3, 2, 1, 1, 1, 0)

Correct answer: (3, 3, 3, 1, 0, 0)

Solution

The 6-tuple (3, 3, 3, 1, 0, 0) is not graphic because the sum of the degrees (10) is odd, which violates the Handshaking Lemma that states the sum of the degrees of a graph must be even, as each edge contributes two to the total degree count.

Related GATE Technical questions

• Let G = (V,E) be a directed graph where V is the set of vertices and E the set of edges. Then which one of the following graphs has the same strongly connected components as G ?
• Consider the following program in C language: #include <stdio.h> main() { int i; int *pi = &i; scanf("%d", pi); printf("%d ", i+5); } Which one of the following statements is TRUE?
• Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time of Depth First Search on G, when G is represented as an adjacency matrix?
• Let P be a quicksort program to sort numbers in ascending order using the first element as the pivot. Let t1 and t2 be the number of comparisons made by P for the inputs [1 2 3 4 5] and [4 1 5 3 2] respectively. Which one of the following holds?
• Which one of the following is TRUE ?
• Match the following: 1) Waterfall model 2) Evolutionary model 3) Component-based software engineering 4) Spiral development a) Specifications can be developed incrementally b) Requirements compromises are inevitable c) Explicit recognition of risk d) Inflexible partitioning of the project into stages

⚔️ Practice GATE Technical free + battle 1v1 →