edited by
7,329 views
36 votes
36 votes

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?

  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)$
edited by

4 Answers

Best answer
52 votes
52 votes

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.

edited by
1 votes
1 votes

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.

undirected graph

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.

0 votes
0 votes

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

Answer:

Related questions

100 votes
100 votes
10 answers
1
8 votes
8 votes
1 answer
2
go_editor asked Jun 15, 2016
2,823 views
If $\text{G}$ is a graph with e edges and n vertices the sum of the degrees of all vertices in $\text{G}$ is$e$$e/2$$e^2$$2 e$
51 votes
51 votes
5 answers
3
gatecse asked Sep 21, 2014
11,367 views
Let $G=(V, E)$ be a graph. Define $\xi(G) = \sum\limits_d i_d*d$, where $i_d$ is the number of vertices of degree $d$ in $G.$ If $S$ and $T$ are two different trees with ...