The Gateway to Computer Science Excellence
+27 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)$
in Graph Theory by Veteran (105k points)
edited by | 2.3k views


I am confused.. please explain?

is it because of Simple Graph(parallel edges not allowed)?


Yes, it is mentioned in the question, "...exists a simple undirected graph.."

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

3 Answers

+42 votes
Best answer

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.

by Boss (11.3k points)
edited by
since we know that no. of vertices having odd degree is even....looking that way....ans c
Well explained
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)
+1 vote

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.

by Loyal (9.9k points)
+1 vote

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

by Boss (11.6k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,313 answers
105,048 users