Question

Show that 1,2,2,3,4 is graphical but that 1,3,3,3 is not. Prove the theorem of Havel-Hakimi that for \(n \geq 1,\) the sequence \(d_{1}, d_{2}, \ldots, d_{n}\) is graphical if and only if \(d_{1}, d_{2} \ldots \ldots d_{n-d_{n}}, d_{n-d_{n}+1}-1, \ldots, d_{n-1}-1\) is graphical.

Short answer

Sequence 1,2,2,3,4 is graphical; 1,3,3,3 is not.

Step-by-step solution

Identify and Sort the Sequence

To determine if a sequence is graphical, first sort the sequence in non-increasing order. For the sequence \(1,2,2,3,4\), the sorted sequence is \(4,3,2,2,1\). For the sequence \(1,3,3,3\), the sorted sequence is already \(3,3,3,1\).

Apply the Havel-Hakimi Algorithm

For the sorted sequence \(4,3,2,2,1\):1. Remove the largest value (4), resulting in \(3,2,2,1\).2. Subtract 1 from the next 4 largest numbers, transforming it to \(2,1,1,0\).3. Resort: Remains \(2,1,1,0\).4. Repeat: Remove 2, transform \(1,0,0\) into \(0,0\).5. All zeros: Thus, it's graphical.For \(3,3,3,1\):1. Remove the largest value (3), resulting in \(3,3,1\).2. Subtract 1 from the next 3 largest numbers (only 3 numbers left): \(2,2,0\).3. Resort as \(2,2,0\).4. Remove 2, transform \(2,0\) into \(1,-1\).5. Negative degree: Not graphical.

Verify Zero Condition

For the sequence \(2,1,1,0\) (from the \(1,2,2,3,4\) reduction), after appropriate steps, we reach all zeros \(0,0\). This confirms graphical nature.For sequence \(3,3,3,1\), we encountered negative degrees, indicating it's not graphical.

Key concepts

Graphical Sequence

A graphical sequence is a list of non-negative integers that represent the degree sequence of a simple graph. It tells us how many edges each vertex in the graph is connected to. For a sequence to be graphical, there must exist some simple graph (a graph without loops or multiple edges) such that these numbers correspond to the vertex degrees.

For example, consider the sequence \(1,2,2,3,4\). This sequence is graphical because it corresponds to a graph where one vertex has degree 1, two vertices have degree 2, one vertex has degree 3, and one has degree 4. An important property of a graphical sequence is that the sum of its numbers (or degrees) should be even. In this case, \(1 + 2 + 2 + 3 + 4 = 12\) which is even, supporting its potential to be graphical.

However, the sequence \(1,3,3,3\) is not graphical. When attempting to create a simple graph from this sequence, we find contradictions such as negative degrees when applying the Havel-Hakimi algorithm, which indicates inconsistencies in achieving a valid graph configuration.

Havel-Hakimi Algorithm

The Havel-Hakimi algorithm is a systematic method used to determine if a sequence of numbers is graphical. It applies a sequence of reductions to simplify and test the sequence progressively.

Here's a simplified guide on how to use it:

• Sort the degree sequence in non-increasing order.
• Remove the first element (the largest degree) from the sequence.
• Subtract 1 from the next 'largest degree' number of elements since this removed largest degree represents connecting edges to other vertices, thus decreasing those vertices' degrees by 1.
• Resort and repeat the process on the new sequence.

If you eventually reduce the sequence to all zeros, the initial sequence is graphical. In our case, the sequence \(4,3,2,2,1\) was reduced successfully to all zeros, confirming its graphical nature. Conversely, the algorithm fails for sequences like \(3,3,3,1\), where negative values emerge, proving it non-graphical.

The Havel-Hakimi theorem backs this algorithm by stating that such reductions preserve the graphical nature when performed consistently and accurately.

Graph Degree Sequence

In graph theory, a degree sequence is a count of the degrees of each vertex in a graph, listed in non-increasing order. It gives a summary of how connected various parts of the graph are.

For a sequence to make sense as a degree sequence of some simple graph, it must satisfy certain conditions:

• The sum of its degrees must be even (because each edge adds exactly 2 to the total degree count).
• No single degree can exceed the number of vertices minus one, because a vertex can't connect to more vertices than exist in the graph.

Considering these rules helps avoid attempting to construct impossible graphs. In practical terms, checking if a sequence like \(1,2,2,3,4\) can be realized involves both logical deductions and algorithms like Havel-Hakimi, to systematically rule out contradictions and verify possibilities.

Understanding degree sequences can assist in designing networks or in analyzing the structure of connectivity in various domains like sociology, biology, or computer science.