3.2. Edge Colouring

Try these first

1. 1.

   What is edge colouring?

   Hint

   Think about how colours differ in a graph.

2. 2.

   What does the edge chromatic number denote?

   Hint

   Consider the minimum colours necessary to avoid conflicts.

3. 3.

   What is the purpose of edge colouring in graph theory?

   • To assign colours to vertices
   • To assign colours to edges
   • To create a complete graph

   Hint

   Think about what graph components we are colouring.

4. 4.

   True or False: The maximum degree of a vertex gives a lower bound for edge chromatic number.

   • True
   • False

   Hint

   Remember how edges are connected to vertices.

5. 5.

   For a graph consisting of 8 nodes with varying degrees, demonstrate the edge colouring process while illustrating the chromatic number.

   Hint

   Keep track of which colours you've assigned.

6. 6.

   Design a scheduling algorithm for a tournament with 10 teams, ensuring no two matches occur on the same day for any team. Calculate the edge chromatic number.

   Hint

   Draw the graph and assign colours carefully, counting distinct colours used.