Guided Practice: Determining the Existence of Simple Graphs for Given Degree Sets

Q1(a). Does a simple graph exist with the degree set {1, 2, 3, 4, 4}?

Background

Topic: Graph Theory – Degree Sequences

This question tests your understanding of degree sequences in simple graphs. You are asked to determine if a simple graph (no loops or multiple edges) can be constructed with the given vertex degrees.

Key Terms and Concepts:

• Simple Graph: A graph with no loops or multiple edges between the same pair of vertices.

• Degree Sequence: A list of vertex degrees (number of edges incident to each vertex).

• Handshaking Lemma: The sum of the degrees of all vertices in a graph equals twice the number of edges.

Key Formulas:

• $\text{Sum of degrees} = 2 \times \text{number of edges}$

Step-by-Step Guidance

1. List the degrees in non-increasing order: $4, 4, 3, 2, 1$.

2. Check if the sum of the degrees is even (required by the Handshaking Lemma): $4 + 4 + 3 + 2 + 1$.

3. If the sum is even, consider whether the sequence can correspond to a simple graph. Use the Havel-Hakimi algorithm or check for obvious contradictions (e.g., a vertex with degree greater than or equal to the number of vertices).

4. Apply the Havel-Hakimi process: Remove the largest degree, subtract 1 from the next largest degrees, and repeat. Does the process end with all zeros?

Try solving on your own before revealing the answer!

Q1(b). Does a simple graph exist with the degree set {1, 1, 2, 3, 4}?

Background

Topic: Graph Theory – Degree Sequences

This question asks you to determine if a simple graph can be constructed with the given degrees.

Key Terms and Concepts:

• Simple Graph

• Degree Sequence

• Handshaking Lemma

Key Formulas:

• $\text{Sum of degrees} = 2 \times \text{number of edges}$

Step-by-Step Guidance

1. Arrange the degrees in non-increasing order: $4, 3, 2, 1, 1$.

2. Calculate the sum of the degrees: $4 + 3 + 2 + 1 + 1$.

3. Check if the sum is even. If not, a simple graph cannot exist.

4. If the sum is even, proceed with the Havel-Hakimi process to test for graphicality.

Try solving on your own before revealing the answer!

Q1(c). Does a simple graph exist with the degree set {2, 2, 2, 2, 2, 2}?

Background

Topic: Graph Theory – Regular Graphs

This question explores whether a regular graph (all vertices have the same degree) can be constructed with the given degrees.

Key Terms and Concepts:

• Simple Graph

• Regular Graph

• Handshaking Lemma

Key Formulas:

• $\text{Sum of degrees} = 2 \times \text{number of edges}$

Step-by-Step Guidance

1. Count the number of vertices: There are 6 vertices, each with degree 2.

2. Calculate the sum of the degrees: $2 + 2 + 2 + 2 + 2 + 2$.

3. Check if the sum is even and if the degree is less than the number of vertices (no vertex can have degree equal to or greater than the total number of vertices in a simple graph).

4. Consider what kind of graph this degree sequence might represent (e.g., a cycle).

Try solving on your own before revealing the answer!

Q1(d). Does a simple graph exist with the degree set {1, 1, 1, 2, 2, 2}?

Background

Topic: Graph Theory – Degree Sequences

This question asks you to determine if a simple graph can be constructed with the given degrees.

Key Terms and Concepts:

• Simple Graph

• Degree Sequence

• Handshaking Lemma

Key Formulas:

• $\text{Sum of degrees} = 2 \times \text{number of edges}$

Step-by-Step Guidance

1. Arrange the degrees in non-increasing order: $2, 2, 2, 1, 1, 1$.

2. Calculate the sum of the degrees: $2 + 2 + 2 + 1 + 1 + 1$.

3. Check if the sum is even. If not, a simple graph cannot exist.

4. If the sum is even, use the Havel-Hakimi process to check for graphicality.

Try solving on your own before revealing the answer!

Q1(e). Does a simple graph exist with the degree set {1, 1, 1, 1, 2, 4, 4}?

Background

Topic: Graph Theory – Degree Sequences

This question tests your ability to analyze degree sequences for the possibility of constructing a simple graph.

Key Terms and Concepts:

• Simple Graph

• Degree Sequence

• Handshaking Lemma

Key Formulas:

• $\text{Sum of degrees} = 2 \times \text{number of edges}$

Step-by-Step Guidance

1. Arrange the degrees in non-increasing order: $4, 4, 2, 1, 1, 1, 1$.

2. Calculate the sum of the degrees: $4 + 4 + 2 + 1 + 1 + 1 + 1$.

3. Check if the sum is even. If not, a simple graph cannot exist.

4. If the sum is even, proceed with the Havel-Hakimi process to check for graphicality.

Try solving on your own before revealing the answer!

Q1(f). Does a simple graph exist with the degree set {0, 1, 3, 4, 4, 5, 7}?

Background

Topic: Graph Theory – Degree Sequences

This question asks you to determine if a simple graph can be constructed with the given degrees, including a vertex of degree 0 and a vertex of degree 7.

Key Terms and Concepts:

• Simple Graph

• Degree Sequence

• Handshaking Lemma

Key Formulas:

• $\text{Sum of degrees} = 2 \times \text{number of edges}$

Step-by-Step Guidance

1. Arrange the degrees in non-increasing order: $7, 5, 4, 4, 3, 1, 0$.

2. Count the number of vertices: There are 7 vertices.

3. Check if any degree is greater than or equal to the number of vertices (in a simple graph, the maximum degree is $n-1$).

4. Calculate the sum of the degrees and check if it is even.

Try solving on your own before revealing the answer!