Question 62

Graph structure of $G$:

• Let the complete bipartite graph $K_{3,4}$ have bipartition $(A, B)$ with $|A| = 3$ and $|B| = 4$.
• Vertex $s$ is added and connected to every vertex of $K_{3,4}$.
• Total vertices in $G$: $|V(G)| = 3 + 4 + 1 = 8$ vertices.

Degrees of vertices in $G$:

• Vertex $s$ is adjacent to all 7 vertices of $K_{3,4} \implies \deg(s) = 7$.
• Each vertex $u \in A$ is adjacent to 4 vertices in $B$ plus vertex $s \implies \deg(u) = 4 + 1 = 5$.
• Each vertex $v \in B$ is adjacent to 3 vertices in $A$ plus vertex $s \implies \deg(v) = 3 + 1 = 4$.
• The maximum degree of $G$ is $\Delta(G) = \deg(s) = 7$.

Chromatic index bounds:

• By definition of proper edge-coloring, all edges incident to a common vertex must receive distinct colors. Thus, the chromatic index $\chi'(G) \ge \Delta(G) = 7$.
• By Vizing's Theorem, $\chi'(G)$ is either $\Delta(G) = 7$ (Class 1) or $\Delta(G) + 1 = 8$ (Class 2).
• Since $G$ has 8 vertices, the maximum size of any matching is $8 / 2 = 4$ edges. Total edges $|E| = (3 \times 4) + 7 = 19$. 7 matchings can accommodate up to $7 \times 4 = 28 \ge 19$ edges, and a valid 7-edge-coloring can be explicitly constructed (Class 1).
• Therefore, the minimum number of colours required is 7.