Question

Let \(d_{1}, d_{2}, \ldots, d_{n}\) be a sequence of distinct integers where \(n \geq 1\) and \(0 \leq d_{i} \leq n-1\) for \(1 \leq i \leq n .\) Prove that such a sequence is not graphical.

Short answer

The sequence is not graphical because not all distinct degrees from 0 to n-1 can coexist in a graph with n vertices.

Step-by-step solution

Understanding the Graphical Sequence

A sequence of integers is termed graphical if it is the degree sequence of some simple graph, meaning it is possible to construct a graph where the degree of each vertex corresponds to the integers in the sequence. To prove a sequence isn't graphical, we must show there's no graph that can have that sequence as its vertex degree sequence.

Degree Sum Condition

A necessary condition for a sequence to be graphical is that the sum of the degree sequence must be even. Given that our sequence has integers from the set \( \{0, 1, \ldots, n-1 \} \), the sum, \( S = d_{1} + d_{2} + \ldots + d_{n} \), can be calculated. Since these are distinct integers, if you choose them from this set, their sum is exactly \( \frac{n(n-1)}{2} \).

Checking Graphical Conditions

For the sequence to be graphical, the sum \( S \) must be even. We check \( \frac{n(n-1)}{2} \). This is the sum of an arithmetic series and is always even because \( n(n-1) \) represents the product of two consecutive numbers, one of which is always even. However, this does not guarantee if the sequence \( d_{1}, d_{2}, \ldots, d_{n} \) matches the vertex degrees needed for any specific graph without repetition.

Applying Havel-Hakimi Algorithm

To further investigate if this sequence is graphical, utilize Havel-Hakimi algorithm which iteratively reduces the sequence. However in the case when using numbers strictly from the set \( \{0, 1, \ldots, n-1 \} \), which are all present due to having \( n \) distinct numbers, such a degree sequence cannot fulfill the criteria at each step without failure because eventually one needed degree will exceed those available.

Conclusion

Summarizing from the above steps, because the sequence uses all integers from \( 0 \) to \( n-1 \), there cannot be any graph with \( n \) vertices since some vertices would share the same degree. Foremost, no graph possible has an exact sequence of one each of all possible lower numbers to the number of vertices in any ordering making all not viable.

Key concepts

Graphical Sequence

A graphical sequence is an important concept in graph theory. It represents a sequence of non-negative integers that corresponds to the degree sequence of a simple graph. In simpler terms, if a sequence is graphical, it means you can find a way to construct a graph where each number in the sequence represents the degree of a vertex in that graph. The concept of a graphical sequence helps in understanding if constructing a graph with certain vertex degrees is possible or not.
To identify if a sequence is graphical, certain properties must be checked. One main property is that the sum of all integers in the sequence should be even. This is because each edge in a graph increases the degree count of two vertices. Thus, only sequences with an even sum can potentially align with the degrees in a simple graph. However, having an even sum does not entirely qualify a sequence as graphical, additional checks, like the Havel-Hakimi algorithm, are often necessary.

Degree Sequence

The term degree sequence refers to a list of vertex degrees (or the number of edges) connected to each vertex in a graph. In practical scenarios like network analysis, determining degree sequences can help in understanding how well-connected the nodes in the network are.
For a sequence to be considered as a degree sequence of a simple graph, it must fulfill specific conditions. First, the sequence must be non-negative, as a vertex cannot have a negative number of connections. Additionally, the sum of the degree sequence should be even, to comply with the properties of undirected graphs where each edge contributes to the degree of two vertices.
An interesting exercise in graph theory involves checking whether a given degree sequence can correspond to a simple graph. By applying methods such as the Havel-Hakimi algorithm, one can ascertain the viability of a sequence as a degree sequence.

Havel-Hakimi Algorithm

The Havel-Hakimi algorithm is a procedure used in graph theory to determine if a sequence of non-negative integers is graphical, i.e., if it is possible to find a simple graph corresponding to a given degree sequence. This algorithm offers a systematic approach by iteratively transforming the sequence while maintaining specific properties until either a realization is constructed or it is proved impossible.
The algorithm consists of several steps:

• Sort the sequence in non-increasing order.
• Select the first element (say, \(d\)) and remove it from the sequence.
• Subtract 1 from the next \(d\) elements of the sequence.
• Check if the sequence is still valid (all elements non-negative).

This process continues until all elements are 0, confirming the sequence is graphical, or a contradiction is reached, proving it is not. Using the Havel-Hakimi algorithm helps examine sequences with systematic clarity, particularly beneficial in mathematical proofs and exercises.

Simple Graph

A simple graph is one of the fundamental models studied in graph theory. It is defined as an undirected graph without any loops or multiple edges between two vertices. The properties of a simple graph make it a crucial subject of study, especially when exploring graphical sequences and degree sequences.
Simple graphs have vertices and edges that signify connections or relations, without any complicated scenarios like double connections or connections back to the same vertex. Thus, the study of simple graphs involves ensuring these basic restrictions are met while constructing or examining any model.
When verifying if a degree sequence can correspond to a simple graph, certain properties must align directly with the characteristics of a simple graph. For instance, each vertex should have its degree satisfied without causing overlaps or exceeding what's feasible, which makes algorithms like Havel-Hakimi indispensable for ensuring that these conditions are met efficiently.