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

edited | 2.3k views
0

ISN'T IT A GRAPH FOR OPTION C?

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

+2

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

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

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

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

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)
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "https://gateoverflow.in/1932/gate2014-1-52", "fetch_time": 1579811091000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2020-05/segments/1579250613416.54/warc/CC-MAIN-20200123191130-20200123220130-00539.warc.gz", "warc_record_offset": 454216937, "warc_record_length": 19621, "token_count": 1058, "char_count": 3439, "score": 4.0625, "int_score": 4, "crawl": "CC-MAIN-2020-05", "snapshot_type": "latest", "language": "en", "language_score": 0.8705133199691772, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00060-of-00064.parquet"}