Question

(i) Find the chromatic polynomials of the six connected simple graphs on four vertices. (ii) Verify that each of the polynomials in part (i) has the form $$ k^{4}-m k^{3}+a k^{2}-b k $$ where \(m\) is the number of edges, and \(a\) and \(b\) are positive constants.

Short answer

The chromatic polynomials of the six connected simple graphs on four vertices can be found by applying the recursive formulas of graph theory. After calculating the polynomials, they should all exhibit the form \( k^{4}-m k^{3}+a k^{2}-b k \), where \( m \) is the number of edges in the graph, and \( a \) and \( b \) are positive constants. The exact polynomial functions will depend on the specific properties of the six selected graphs.

Step-by-step solution

Identify the graphs

The first step towards solving this problem is to identify the six simple connected graphs on four vertices. For simplicity purposes, let's call the graphs G1 to G6.

Compute chromatic polynomials

Next, compute the chromatic polynomials \( P_k(G) \) of each graph. Remember to apply the recursive formula for deleting an edge if it's not a cycle and contracting an edge if it's a cycle in the graph. This may result in values such as \( k(k - 1)^{n-1} \), where \( n \) is the number of vertices and \( k \) is any natural number.

Verify polynomials' form

After obtaining the chromatic polynomials of the graphs, the next step is to verify that they all exhibit the form \( k^{4}-m k^{3}+a k^{2}-b k \), where \( m \) is the number of edges in the graph, and \( a \) and \( b \) are positive constants. Each polynomial might need to be expanded and simplified to match the required form.

Key concepts

Graph Theory

Graph theory is a fascinating area of mathematics concentrating on the study of graphs, which are structures made up of vertices (or nodes) connected by edges. It is the foundation of many scientific fields and applications, ranging from computer networking to sociology.

In essence, a graph is a set of objects where some pairs of the objects are connected by links. The interconnected objects are known as vertices or nodes, and the links that connect the vertices are called edges. In a 'simple graph,' which is often the focus of many introductory graph theory problems, there are no loops (edges connected at both ends to the same vertex) and no more than one edge between any two different vertices.

Understanding graph theory is critical when facing problems such as finding the shortest path, optimizing network designs, or even determining the most efficient way to schedule tasks. In the context of our exercise, graph theory principles are applied to define and solve the problem of graph coloring through the use of chromatic polynomials.

Connected Graphs

In graph theory, a graph is considered connected if there is a path between every pair of vertices. This means that you can start at any vertex and reach any other through a sequence of edges, no matter where you start or end. Connected graphs are important because they illustrate how components of a system are linked.

Importance of Connected Graphs

Consider a network of computers or roads—each point of interaction represents a vertex, and the connections between them are edges. If the graph representing these interactions is connected, it means there's always a way to get from one point in the network to another.

Connected graphs are pivotal when discussing chromatic polynomials, as they are the focus of our exercise. Each of the six graphs on four vertices we work with in the exercise must be connected. This connectivity ensures that each vertex has an impact on the coloring of the graph, which is manipulated in the computation of chromatic polynomials.

Graph Coloring

Graph coloring is a way of assigning labels, commonly referred to as 'colors,' to elements of a graph subject to certain constraints. In vertex coloring, for example, no two adjacent vertices can share the same color.

This concept is not only theoretical but also has practical applications, such as in scheduling, where different tasks may be represented by vertices, and edges represent conflicts between tasks that cannot be conducted at the same time. Finding a color assignment that uses as few colors as possible, known as the chromatic number, is a common goal. This is where the chromatic polynomial comes into play.

Chromatic Polynomial

The chromatic polynomial of a graph is a function that gives the number of ways to color the graph using no more than k colors, where k is a natural number. It is determined by the structure of the graph—primarily its edges and their arrangement.

In the exercise we're considering, the chromatic polynomials for simple connected graphs on four vertices are investigated. These polynomials reveal the relationships between the number of edges (m) and the possible colorings for a given number of colors (k), encapsulated within the set formula provided. By exploring the chromatic polynomial, one can gain deeper insights into the complexities of graph coloring and its various applications.