GATE CSE 2014 Set 1 | Question: 52

Question

An ordered $n-$tuple $(d_1, d_2,\ldots,d_n)$ with $d_1 \geq d_2 \geq \ldots \geq d_n$ is called graphic  if there exists a simple undirected graph with $n$ vertices having degrees $d_1,d_2,\ldots,d_n$ respectively. Which one of the following $6$-tuples is NOT graphic?

• A. $(1,1,1,1,1,1)$
• B. $(2,2,2,2,2,2)$
• C. $(3,3,3,1,0,0)$
• D. $(3,2,1,1,1,0)$

Comments

Apply Havel Hakimi procedure you will find the option c degree sequence is invalid.

---

A. 3 line graph with 2 vertices.

B. Two triangle.

Graph can be disconnected.

---

Graph you have shown is not SIMPLE graph at first,, because in simple graph there cant be multiple edges

Answer 1

This can be solved using havel-hakimi theorem.

$\text{The idea is simple :}$ Remove a vertex, which results into decrease of degree by $1$ of each vertex which was connected to it. Keep removing like this, and if we get any negative degree, the degree sequence was not possible.

We need not check $\left(A\right)$ and $\left(B\right)$ as they are clearly graphs : $\left(A\right)$ is $3$ disconnected edges and$\left(B\right)$ is $2$ disconnected triangles.

For $\left(C\right)$, we remove first vertex of degree $3$, and thus decrease degree by $1$ of next $3$ vertices, so we get $\left(2,2,0,0,0\right)$, then we remove vertex of degree $2$, and decrease degree of next $2$ vertices to get $\left(1,-1,0,0\right)$. Since we get negative degree, original degree sequence is impossible.

For $\left(D\right)$ : $\left(3,2,1,1,1,0\right) \Rightarrow \left(1,0,0,1,0\right)$. Now since this list is not sorted (which is required to apply further steps of algorithm), we sort it to get $\left(1,1,0,0,0\right)$. Then we continue our algorithm on this list to get $\left(0,0,0,0\right)$, which is valid ($4$ isolated vertices).

So (C) is answer.

Comments

We need not check (A) and (B) as they are clearly graphs : (A) is 3 disconnected edges, (B) is 2 disconnected triangles. explain this pls how can draw ?

---

sum of all the degree should be even,  option c) sum of all degree is 7 (NOT EVEN)

---

@register_user_19 sum of degrees is 10, not 7

Answer 2

The Havel–Hakimi algorithm is an algorithm in graph theory solving the graph realization problem, i.e. the question if there exists for a finite list of nonnegative integers a simple graph such that its degree sequence is exactly this list. - Wikipedia
C)333100 = > 22000 = >1-100 => so C is not graphic

Answer 3

The required graph is not possible with the given degree set of (3, 3, 3, 1, 0, 0). Using this 6-tuple the graph formed will be a Disjoint undirected graph, where the two vertices of the graph should not be connected to any other vertex ( i.e. degree will be 0 for both the vertices ) of the graph. And for the remaining 4 vertices the graph need to satisfy the degrees of (3, 3, 3, 1).

Let's see this with the help of a logical structure of the graph :

Let's say vertices labelled as <ABCDEF> should have their degree as <3, 3, 3, 1, 0, 0> respectively.

Now E and F should not be connected to any vertex in the graph. And A, B, C and D should have their degree as <3, 3, 3, 1> respectively. Now to fulfill the requirement of A, B and C, the node D will never be able to get its degree as 1. It's degree will also become as 3. This is shown in the above diagram.

Hence tuple <3, 3, 3, 1, 0, 0> is not graphic.

Answer 4

The correct option is C (3, 3, 3, 1, 0, 0)
Use the Havell-hakimi algorithm.