Determine if a graph exists knowing the degree of its vertices

Suppose it is simple and without loops.

If that one exist then if we delete node with degree $9$ and it edges, we would get a graph:

$$7,7,7,5,4,3,3,1,1$$

now if we delete node of degree $7$ and it edges we get

$$6,6,4,3,2,2,1,0\;\;\;\;{\rm or} \;\;\;\;\geq 6,?,?,?,?,?,0,0$$

Second situation is impossible since at least one node of degree $0$ must be connected with first one with degree at least 6.

So suppose 1. situation is possible, then it is also: $$5,3,2,1,1,0$$

but this is actualy impossible (since at least one node of degree $0$ must be connected with first one with degree at least 5).

So such a graph does not exist.


The answer is FALSE.

We proceed with the Havel–Hakimi Theorem, which determines whether a degree sequence can represent a simple graph.

Applying this theorem, we note that the original degree sequence is graphical if and only if the degree sequence given by $\{7, 7, 7, 5, 4, 3, 3, 2, 1\}$ is graphical. We can keep on reiterating to get the following degree lists:

$$\{6, 6, 4, 3, 2, 2, 1, 0\} \rightarrow \{5, 3, 2, 1, 1, 0, 0\} \rightarrow \{2, 1, 0, 0, 0, -1\}$$

But, the last degree list is clearly not graphical: it has an edge with a negative degree! So, the answer is false.

Tags:

Graph Theory

Combinatorics

Discrete Mathematics

Related

Confusing Lagrange multipliers question A series whose convergence is equivalent to the Riemann hypothesis Alternative proof that $U(n^2-1)$ is not cyclic for $n>2$. What is the motivation of defining weak derivative as it is? Second difference on the sum of extreme values of square numbers Drawing balls of an urn, probability of one colour run out (with replacement) Understanding some proofs-without-words for sums of consecutive numbers, consecutive squares, consecutive odd numbers, and consecutive cubes Does an attractive fixed point always have a derivative between 1 and -1? Proving $\binom{n + m}{r} = \sum_{i = 0}^{r} \binom{n}{i}\binom{m}{r - i}$ Conjecture: $\sum\limits_{n\geq0}\left(\frac12\right)^n\prod\limits_{k=1}^{n}\frac{2n-2k+1}{2n-2k+2}=\sqrt2$ How do we really get the angle of a vector from the components? In an acute triangle ABC, the base BC has the equation $4x – 3y + 3 = 0$. If the coordinates of the orthocentre (H) and circumcentre (P).

Recent Posts