Problem 65 - Discrete Mathematics with Applications

Question

Let \(v_{1}, \ldots, v_{n}\) be n vertices with degrees \(\operatorname{deg}\left(v_{1}\right), \ldots, \operatorname{deg}\left(v_{n}\right),\) respectively, such that \(\sum_{i=1}^{n} \operatorname{deg}\left(v_{i}\right)\) is even. Prove that there exists a graph satisfying these conditions. [Hint: Let \(\sum_{i=1}^{n} \operatorname{deg}\left(v_{i}\right)=2 e .\) Use induction on e. \(]\)

Step-by-Step Solution

Answer

In order to prove that a graph exists satisfying the given conditions, we use induction on the number of edges, e. For the base case, we consider e = 0, which implies a graph with n isolated vertices (vertex degree sum = 0). For the induction hypothesis, assume the statement holds true for e = k. Then for the induction step, consider the case when the total vertex degree is \(2(k+1)\). We consider two cases: (1) all vertices have even degree, and (2) at least two vertices have odd degree. In both cases, by choosing two vertices, decreasing their degrees, and using the induction hypothesis, we can construct a graph satisfying the given conditions. Thus, the statement holds true for all even sums of vertex degrees.

Step 1: Base Case

For the base case, we have e = 0, which means \(\sum_{i=1}^{n} deg(v_i) = 0\). This implies that all vertices have degree 0. We can construct a graph with n isolated vertices (i.e., a graph with no edges), satisfying the given conditions.

Step 2: Induction Hypothesis

Assume that our statement holds true for e = k, i.e., if \(\sum_{i=1}^{n} deg(v_i) = 2k\), then there exists a graph satisfying these conditions.

Step 3: Induction Step

Now, consider the case when the total vertex degree is \(\sum_{i=1}^{n} deg(v_i) = 2(k+1)\). We can sort vertices in descending order based on their degrees: \(deg(v_1)\geq deg(v_2)\geq ... \geq deg(v_n)\). As the total vertex degree is even, there are two cases to consider: Case 1: All vertices have even degree. In this case, we can construct a graph as follows: 1. Pick any two vertices with even degrees, say \(v_i\) and \(v_j\). 2. Decrease their degrees by one, i.e., set \(deg'(v_i) = deg(v_i) - 1\) and \(deg'(v_j) = deg(v_j) - 1\). 3. The new vertex set \(V'\) will have total vertex degree \(\sum_{k=1}^{n} deg'(v_{k}) = 2k\), e reduced by 1. 4. By the induction hypothesis, there exists a graph satisfying these conditions for vertex set \(V'\). 5. Finally, add the edge between vertices \(v_i\) and \(v_j\) to obtain the graph satisfying the original vertex set \(V\). Case 2: At least two vertices have odd degree. In this case, we can construct a graph as follows: 1. Pick any two vertices with odd degrees, say \(v_i\) and \(v_j\). 2. Decrease their degrees by one, i.e., set \(deg'(v_i) = deg(v_i) - 1\) and \(deg'(v_j) = deg(v_j) - 1\). 3. The new vertex set \(V'\) will also have total vertex degree \(\sum_{k=1}^{n} deg'(v_{k}) = 2k\), e reduced by 1. 4. By the induction hypothesis, there exists a graph satisfying these conditions for vertex set \(V'\). 5. Finally, add the edge between vertices \(v_i\) and \(v_j\) to obtain the graph satisfying the original vertex set \(V\). Since we've shown that we can construct a graph satisfying the given conditions for \(\sum_{i=1}^{n} deg(v_i) = 2(k+1)\) under both cases, we can conclude that the statement holds true for all e. Therefore, if the sum of vertex degrees is even, there exists a graph satisfying these conditions.

Key Concepts

Degree Sequence

A degree sequence in graph theory is a list of degrees (or a sequence) of each vertex in a graph. The degree of a vertex refers to the number of edges connected to it. When we write a degree sequence for a graph with vertices \(v_1, v_2, \ldots, v_n\), it is represented as \(\text{deg}(v_1), \text{deg}(v_2), \ldots, \text{deg}(v_n)\). This sequence helps in understanding the structure and properties of the graph.

One important aspect of degree sequences is that the sum of all degrees in a graph is always even. This is because each edge contributes exactly two to the total degree count—one for each of its endpoints. Therefore, it becomes essential in graph construction and analysis to ensure that any valid graph under consideration must have an even degree sum.

To comprehend degree sequences fully, remember:

• The sequence must be non-increasing if you want to work with it easily—meaning the degrees are sorted from the largest to the smallest.
• The even sum of degrees holds true for all simple graphs, i.e., graphs without loops or multiple edges between vertices.

Understanding degree sequences can quickly tell us about possible connections or disconnections between vertices in a graph.

Induction Proof

Induction proof is a mathematical technique used to establish the truth of an infinite sequence of statements. It consists of two main steps: the base case and the induction step. This method is particularly useful in graph theory to demonstrate properties or the existence of graphs satisfying certain conditions, such as having a particular degree sequence.

Let's break down the parts of induction:

• Base Case: Verify if the statement holds for the initial instance (often the smallest value, like \(e=0\) in our problem). Here, a graph with zero edges means isolated vertices, which perfectly fits the base case.
• Induction Step: Assume that the statement is true for a certain case \(k\), and demonstrate it's also true for \(k+1\). This logical step builds upon the assumption and helps expand the proof further.

By successfully completing both steps, we confirm the property for all integers involved. This powerful method allows us to handle even challenging problems like constructing specific graphs, offering a systematic way to prove existence and properties.

Graph Construction

Constructing a graph from a given degree sequence is a critical skill in graph theory. The process often begins by verifying that the degree sequence is valid, meaning that it follows all necessary rules and can indeed represent a graph. When the degree sequence is sorted in non-increasing order, you can begin creating the graph by connecting vertices accordingly.

Here's a simple outline of the process for constructing a graph:

• Start with vertices: Ensure you have a vertex for each degree in your sequence.
• Connect vertices: Use the degrees to decide which vertices will have edges between them, prioritizing those with higher unsatisfied degree needs.
• Adjust degrees: After adding an edge, decrease the degree of involved vertices by one until all degree requirements are satisfied.

This process can be made simpler with tools like the Havel-Hakimi algorithm that iteratively adjusts sequences to fulfill graph creation rules.

Constructing graphs from degree sequences ensures a real-world application of structures in theoretical studies and practical implementations alike.

Even Degree Sum

An even degree sum is a fundamental property in graph theory. The concept is rooted in the idea that every edge in a graph increases the degree count of two vertices. Thus, whether looking at simple undirected graphs or other types, the sum of all vertex degrees must be even.

Consider a simple undirected graph. If you sum up all vertex degrees to find that it equals \(2e\), where \(e\) is the number of edges, you affirm the evenness. This concept is pivotal, as it determines whether or not a graph can be constructed from a given degree sequence.

The steps involved are:

• Always verify that the sequence's sum is even before attempting construction.
• If the sum is not even, you cannot form a proper graph just from that sequence.
• This even sum is also crucial when using the induction method to show the existence of graphs for particular sequences.

Being aware of the even degree sum ensures you’re on the right path to produce possible graph structures, thereby aligning practical tasks with theoretical concepts in graph studies.