6.2. Question 11: Edge Chromatic Number of Complete Graphs

Based on these information, I will try to solve question 11 where I want to find the edge chromatic number of a complete graph with n nodes and my solution will be divided into 2 cases depending upon whether my n is odd or even.

In this part, we are introducing the concept of edge chromatic number, which is the minimum number of colors needed to color the edges of a graph such that no two adjacent edges have the same color. The solution will focus on complete graphs (denoted as K_n) and consider two scenarios based on whether the number of nodes (n) is odd or even.

Think of a sports league where each match represents an edge and each team represents a vertex. The edge chromatic number corresponds to the number of different days we can schedule matches, ensuring no team plays more than once a day.

So, remember, from the previous question, I know that if your n is even then you can use 1 colour and colour at most edges, whether indeed you will be able to colour edges or not that depends upon the structure of your graph, but at max you can colour edges using a single colour.

When n is even, we can color the edges of the complete graph using a limited number of colors. The maximum instance is determined by the formula which allows us to color a certain number of edges with a single color. Here, it’s suggested that up to a certain threshold based on the graph's structure, we can achieve valid edge coloring.

Imagine scheduling matches for an even number of teams. You can efficiently arrange matches so that no team plays more than one match on the same day, thus minimizing the number of days required for the entire tournament.

Whereas if n is odd, then from my analysis of question 10, I know that through 1 colour I can take care of at most number of edges. And I have to take care of n bunches of number of edges. So, that means I will require at least n colours if my n is odd.

For odd n, the situation becomes more complex. The analysis indicates that we need an increased number of colors—specifically n colors—to ensure that every edge can be colored without adjacent edges sharing the same color. This is because, with an odd number of vertices, it becomes impossible to color more than a certain number of edges with a single color without creating conflicts.

Returning to our sports league analogy, if we have an odd number of teams, we might need as many days as there are teams to ensure that each team plays without conflict. Each day's schedule represents a different color for the edges.

Now what I will show is I will show that these bounds on the edge chromatic numbers, which were the lower bounds because they were the least number of colours which are required, they are actually tight in the sense I will give you a constructive colouring, a concrete colouring for colouring the edges of a complete graph with n nodes where n is even.

The text explains a constructive method to color the edges of a complete graph for the case where n is even. By showing practical examples or constructing a real-coloring scheme, the author illustrates that the previously established thresholds for edge coloring can be achieved exactly, confirming that the formula for lower bounds on colors needed is not just theoretical but can be put into practice.

Imagine planning the tournament schedule for 8 teams (even number). By organizing matches with a step rotation strategy, every team competes without overlapping their matches at any time, demonstrating the achievable edge coloring scheme.

Now let us see how exactly we can colour all the edges of a complete graph with n nodes where n is odd. And I will be using exactly n colours, which is optimal because the lower bound says that for n being odd, I need at least n colours.

For odd n, the approach involves transforming the setup by adding a dummy node, allowing you to use an even graph coloring approach and then removing this dummy node after coloring. This technique utilizes the even phase’s coloring properties and while being optimal within the necessary constraints, it showcases a strategic way to successfully manage odd scenarios.

Consider a basketball league with 7 teams. By bringing in an imaginary 8th team purely for scheduling, you can find a fair play schedule for matches. Once structured, you disregard the 8th team’s matches while keeping the schedule for the real teams.

--