Question

(i) Draw a graph on six vertices with degree sequence \((3,3,5,5,5,5)\); does there exist a simple graph with these degrees? (ii) How are your answers to part (i) changed if the degree sequence is \((2,3,3,4,5,5)\) ?

Short answer

It is not possible to draw a simple graph with degree sequence (3,3,5,5,5,5) due to the Handshaking theorem. However, it is possible to draw a simple graph with degree sequence (2,3,3,4,5,5) because the sum of the degrees equates to an even number.

Step-by-step solution

Graph creation for the degree sequence (3,3,5,5,5,5)

Start with six vertices. Connect two vertices each having degree 3 with four vertices each having degree 5. Always keep a count on the number of edges hosted on each vertex to make sure each vertex hosts the correct number of edges and no more. Make sure that no vertex connects to itself and there are no multiple edges between any two vertices (as it's supposed to represent a simple graph). The sum of the degrees of the vertices is 2(number of edges), from the Handshaking Theorem. In this case 3+3+5+5+5+5 = 26, which is not an even value. This means it is impossible to create a simple graph with all vertices having these degrees.

Graph creation for the degree sequence (2,3,3,4,5,5)

Again, start with six vertices. Connect one vertex with degree 2 with the rest of vertices per their degrees. Continue this process for vertex with degree 3,4,5. Ensure that each vertex hosts the correct number of edges, and the graph does not include any loops or multiple edges. Now, calculate the sum of degrees. It is 2+3+3+4+5+5 = 22, which is an even number, satisfying the Handshaking Theorem. This means it is possible to draw a simple graph with this degree sequence.

Key concepts

Degree Sequence

In graph theory, the degree sequence of a graph is a list of vertex degrees, which are the number of edges connected to each vertex. It's usually represented in non-increasing order, meaning the numbers are arranged from highest to lowest. Understanding a degree sequence helps us determine properties of the graph, such as whether it's simple or not.

A simple graph is one that has no loops (a vertex connected to itself) and no multiple edges between any pair of vertices. Hence, when analyzing a degree sequence, we must ensure that these criteria are met in any potential graph configuration. For instance, in the exercise above, graphing with the degree sequence \((3, 3, 5, 5, 5, 5)\) was impossible in the domain of simple graphs because it's not consistent with necessary conditions.

• Each vertex can connect only through allowed edges.
• Any single degree can't exceed half the total number of vertices if connected distinctly.

The exercise highlights this as the sum of degrees must be even, which leads us to the Handshaking Theorem.

Simple Graph

A simple graph is a fundamental concept in graph theory characterized by its lack of loops and multiple edges. In practical terms, this means each edge connects two different vertices, and there is only one edge connecting each pair of vertices.

Constructing a simple graph involves careful planning to align with the given degree sequence. For example, when a graph needs to be formed using the sequence \((2, 3, 3, 4, 5, 5)\):

• Start with six vertices, labeled and organized for the task.
• Connect these vertices to ensure each fulfills its role in the degree sequence.
• Avoid tasks that breach the simple graph rule, such as creating multiple connections between the same two vertices.

The procedure requires checking each connection meticulously. This task is compounded by integrating the degrees to retrieve a suitable configuration.

Handshaking Theorem

The Handshaking Theorem is a curious yet vital principle in graph theory. It states that in any undirected graph, the sum of all vertex degrees is equal to twice the number of edges. In simpler terms, for every handshake at a gathering, two people are involved, and thus the count must be even. Merely understanding this concept clarifies why a degree sequence like \((3, 3, 5, 5, 5, 5)\) couldn't support a simple graph. Its summed degree, 26, turned out to be unsuitable because it's an odd result.

The theorem's utility becomes evident when constructing or validating graphs:

• Before connecting vertices, check if the degree sum is even.
• Utilize the theorem to gauge the viability of a graph setup.

This theorem ensures that when the connections are made, each vertex comfortably fits into the wider network without any leftover edges or discrepancies. Thus, it serves as a crucial checkpoint during graph creation.