5,246 views

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

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

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.

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)

sum of degrees is 10, not 7

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

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.

1
19,764 views