Question

Let \(d_{1}, d_{2}, \ldots, d_{n}\) be a nondecreasing sequence of non-negative integers representing the degrees of the vertices of some graph. Prove that \(\sum_{i=1}^{n} d_{i}\) is even. Is the converse to this result true?

Short answer

The sum of vertex degrees in a graph is always even, but not all integer sequences with even sums are realizable as graph degrees.

Step-by-step solution

Understanding the Problem

We need to show that in any graph, the sum of the degrees of all vertices is an even number. This requires applying a property from graph theory that connects vertex degrees to the structure of the graph, specifically the number of edges.

Graph Theory Property

Recall that a fundamental property in graph theory is that the sum of the degrees of all vertices in a graph is twice the number of edges. This is because each edge contributes twice to the vertex degree sum (once for each end of the edge). Mathematically, this is \[ ext{Sum of degrees} = 2 imes ( ext{Number of edges}) \] which is clearly an even number.

Applying the Property

Since the sum of the degrees is equal to twice the number of edges, it must be even, as two times any integer results in an even number. Thus, for any graph, the sum of degrees \( \sum_{i=1}^{n} d_{i} \) is even.

Checking the Converse

The converse would state that if the sum of the degrees is even, then there exists a graph with these degrees. However, this is not necessarily true, because having an even sum does not guarantee that there is a corresponding graph structure. For example, a degree sequence might require all vertices to be connected, which might be impossible if some conditions aren't met (such as the handshaking lemma or graphical sequence conditions).

Conclusion

While the sum of the degrees of vertices in a graph is always even, the converse doesn't hold. Not every non-negative integer sequence with an even sum can be realized as the degree sequence of a graph unless specific conditions are met.

Key concepts

Degree Sequence

In graph theory, a degree sequence is a sequence of non-negative integers representing the degrees of the vertices in a graph. The degree of a vertex is simply the number of edges incident to it. When we list these degrees, we arrive at the degree sequence.

A valid degree sequence should satisfy certain conditions to be considered **graphical**, which means that it can actually correspond to a graph. These conditions ensure that the degrees of its vertices can construct a meaningful graph. Checking the properties of a degree sequence is essential for graph realization problems.

Vertex Degree

The vertex degree is a fundamental concept in graph theory. It refers to the number of connections (edges) a vertex has with other vertices in a graph.

Understanding vertex degree is crucial because it helps in characterizing the properties of the graph. For instance:

• A vertex with degree zero is an isolated vertex.
• The vertex with the highest degree is often called the **maximal degree vertex**.

Vertex degree provides insights into the connectivity and complexity of the graph's structure. Whether working on simple structures or complex networks, knowing the degrees of vertices helps in analyzing how connected or sparse the network is.

Edge Count

The edge count of a graph refers to the total number of edges present in the graph. This count directly affects the properties of the graph, such as its connectivity and structure.

The edge count is connected to the degree sequence through the formula: \[ \text{Sum of degrees} = 2 \times \text{Edge count} \]

This equation is pivotal because it ties together the vertex degrees and edges. Since each edge contributes to the degree of two vertices (one at each end), the sum of all vertex degrees is always twice the number of edges, ensuring an even total.

Graphical Sequence

A **graphical sequence** is a special type of degree sequence that can correspond to a valid graph. Not every sequence of integers can make up the degrees of a graph's vertices.

For a sequence to be graphical, it must satisfy particular criteria, such as the **Havel-Hakimi algorithm** or **Erdős–Gallai theorem** conditions, which check if a set of numbers can be rearranged to form a graph.

Graphical sequences help determine if it's possible to draw a graph with a given set of degrees. Ensuring that a sequence is graphical is essential before attempting to construct a graph from it.

Handshaking Lemma

The Handshaking Lemma is a classic result in graph theory that states the sum of the degrees of all vertices in a graph is twice the number of edges. This conclusion follows naturally since every edge adds to the degree count of exactly two vertices.

This lemma provides fundamental insight into why the sum of the vertex degrees in a graph is always even, a concept that applies to any simple graph.

The lemma helps prevent impossible degree sequences by ensuring that the total vertex degree is aligned with the graph's edge configuration, thereby balancing the graph's interactions.