Graph $G$ is obtained by adding vertex $s$ to $K_{3,4}$ and making $s$ adjacent to every vertex of $K_{3,4}$. The minimum number of colours required to edge-colour $G$ is _______.

Let the bipartite sets of $K_{3,4}$ be $U$ with $|U|=3$ and $V$ with $|V|=4$.

The vertex $s$ is connected to all vertices of $K_{3,4}$. Thus, the degrees of the vertices in $G$ are:

• $\deg(s) = |U| + |V| = 3 + 4 = 7$

• For $u \in U$, $\deg(u) = 4 + 1 = 5$

• For $v \in V$, $\deg(v) = 3 + 1 = 4$

The maximum degree of $G$ is $\Delta(G) = \deg(s) = 7$.

By Vizing's Theorem, the chromatic index (edge chromatic number) $\chi^{\prime}(G)$ satisfies $\Delta(G) \le \chi^{\prime}(G) \le \Delta(G) + 1$, meaning $\chi^{\prime}(G)$ is either $7$ or $8$.

Graph $G$ has $|V(G)| = 3 + 4 + 1 = 8$ vertices (an even number) and $|E(G)| = (3 \times 4) + 7 = 19$ edges. Since $G$ is Class 1, its edges can be properly colored using $\Delta = 7$ colors.

Therefore, the minimum number of colours required to edge-colour $G$ is 7.