GATE CS 2020 Q52 — Graphs: Connectivity, Matching, Colouring

To find the minimum number of colors required to edge-color the graph $G$ (the chromatic index $\chi'(G)$), we first determine its maximum degree $\Delta(G)$.

Let the bipartite graph be $K_{3,4}$ with partitions $V_1 = \{x_1, x_2, x_3\}$ and $V_2 = \{y_1, y_2, y_3, y_4\}$.

• The degree of each vertex in $V_1$ is $4$.
• The degree of each vertex in $V_2$ is $3$.

A new vertex $s$ is added and made adjacent to all $7$ vertices of $K_{3,4}$. Thus, the degrees in $G$ are:

• $d(s) = 7$
• $d(x_i) = 4 + 1 = 5$ for each $x_i \in V_1$
• $d(y_j) = 3 + 1 = 4$ for each $y_j \in V_2$

The maximum degree of $G$ is $\Delta(G) = 7$. By Vizing's Theorem, the chromatic index $\chi'(G)$ is either $\Delta(G) = 7$ or $\Delta(G) + 1 = 8$.

We can construct a valid $7$-edge-coloring of $G$ using colors $\{1, 2, 3, 4, 5, 6, 7\}$ as follows:

1. Color the edges of $K_{3,4}$ using $4$ colors $\{1, 2, 3, 4\}$ such that the edge $x_i y_j$ gets color $M_{i,j}$ from the following Latin-like rectangle: $$M = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 \\ 3 & 4 & 1 & 2 \end{pmatrix}$$
2. Color the edges incident to $s$ connected to $V_1$ using the remaining colors:
   • Color of $s x_1 = 5$
   • Color of $s x_2 = 6$
   • Color of $s x_3 = 7$
3. Color the edges incident to $s$ connected to $V_2$ using the unique missing color from $\{1, 2, 3, 4\}$ at each $y_j$:
   • At $y_1$, the missing color is $4$, so color $s y_1 = 4$.
   • At $y_2$, the missing color is $1$, so color $s y_2 = 1$.
   • At $y_3$, the missing color is $2$, so color $s y_3 = 2$.
   • At $y_4$, the missing color is $3$, so color $s y_4 = 3$.

This assignment is a valid edge-coloring of $G$ using exactly $7$ colors. Thus, the minimum number of colors required is $7$.