Chapter 6 Symmetric latin squares

Introduction \[sec4000\] The aim of this chapter is to give necessary and sufficient conditions for embedding a symmetric latin rectangle in a symmetric latin square with prescribed external off-diagonal cells. This is a small step towards generalising Theorem \[thm1440\] to give necessary and sufficient conditions for embedding a symmetric latin rectangle in a symmetric latin square with prescribed external cells.

Inevitably the approach taken in this chapter is to consider the analogous problem of embedding a proper \(C_{[n]}\)-edge-coloured \(r\)-free-type graph of order \(n\) in a proper \(C_{[n]}\)-edge-coloured complete graph.

Throughout this chapter \(C=C_{[n]}\) and, if \(H\) is an \(r\)-free-type graph of order \(n\) then \(V=V(H^{\star})=\{v_i\,|\,i\in [r]\}\).

The Ryser condition and loop admissibility \[sec4010\] In this section the first aim is to prove, in Lemma \[lem4040\], the necessity of being Ryser for embedding a proper \(C\)-edge-coloured \(r\)-free-type graph of order \(n\) in a proper \(C\)-edge-coloured complete graph of order \(n\). The second aim is to prove, in Lemma \[lem4060\], the necessity of being admissible.

\[def4020\] A proper \(C\)-edge-coloured \(r\)-free-type graph \(\cH\) of order \(n\) is Ryser if and only if (\[eqn4030\]) holds for all \(c_k\in C\) \[\label{eqn4030} 2\ek+\lk\geq 2r-n+2\Ek+\Lk\]

\[ex4030\] Let \(\cH\) be the proper \(C_{[8]}\)-edge-coloured \(4\)-free-type graph of order 8 in Figure \[fig4035\]. If \(c_k\in C_{[8]}\backslash\{c_1,c_2,c_6\}\) then \(2r-n+2\Ek+\Lk=0\) for all \(c_k\in C_{[8]}\backslash\{c_1,c_2,c_6\}\). If \(c_k\in\{c_2,c_6\}\) then \(2r-n+2\Ek+\Lk=1\) and \(2r-n+2\eps(c_1)+\lambda(c_1)=2\). Therefore \(\cH\) is Ryser because, trivially, \(2\ek+\lk\geq 0\) for all \(c_k\in C\), \(2\ek+\lk\geq 1\) for \(c_k\in\{c_2,c_6\}\) and \(2e(c_1)+l(c_1)=2\).

A proper \(C_{[8]}\)-edge-coloured \(4\)-free-type graph of order \(8\)

\[lem4040\] If a proper \(C\)-edge-coloured \(r\)-free-type graph \(\cH\) of order \(n\) can be embedded in a proper \(C\)-edge-coloured complete graph of order \(n\) then \(\cH\) is Ryser.

There are \(r-(2\ek+\lk)\) vertices in \(V\) which in \(H^{\star}\) are the end of no edge of colour \(c_k\in C\). Therefore, if \(\cH\) is embedded in a proper \(C\)-edge-coloured complete graph \(\cK\) of order \(n\), there are \(r-(2\ek+\lk)\) edges \(vw\) of colour \(c_k\in C\) with \(v\in V\) and \(w\in V(F\cup\Lambda)\). Of these, because \(\cH\) is proper, none have as an end any of the \(2\Ek+\Lk\) vertices which have an end in common with either a free-edge of \(H\) or free-loop of \(H\) of colour \(c_k\). Therefore, all must have as an end one of the remaining \((n-r)-(2\Ek+\Lk)\) vertices of \(V(F\cup\Lambda)\). It follows that \((n-r)-(2\Ek+\Lk)\geq r-(2\ek+\lk)\).

\[def4050\] A proper \(C\)-edge-coloured \(r\)-free-type graph \(\cH\) of order \(n\) is admissible if and only if either \(n\) is odd and \(\lk+\Lk\leq 1\) holds for all \(c_k\in C\) or \(n\) is even and \(o(\cH)\leq 2|F|\).

\[ex4055\] If \(\cH\) is the \(C_{[8]}\)-edge-coloured \(4\)-free-type graph of order \(8\) in Figure \[fig4035\] then \(O(\cH)=\{c_5,c_6\}\). Therefore \(\cH\) is admissible, because \(2|F|=2=o(\cH)\).

\[lem4060\] If a proper \(C\)-edge-coloured \(r\)-free-type graph \(\cH\) of order \(n\) can be embedded in a proper \(C\)-edge-coloured complete graph of order \(n\) then \(\cH\) is admissible.

Suppose \(\cH\) can be embedded in a proper \(C\)-edge-coloured complete graph \(\cK\) of order \(n\). If \(n\) is odd then \(\lrkkk+\Lrkkk=1\) for all \(c_k\in C\). Therefore, as \(\cH\) is embedded in \(\cK\) and hence every loop of colour \(c_k\) in \(\cH\) is a loop of colour \(c_k\) in \(\cK\), it follows that \(\lk+\Lk\leq\lrkkk+\Lrkkk=1\). If \(n\) is even then \(O(\cK)=\emptyset\). Therefore if \(c_k\in O(\cH)\) it follows that there is a loop of colour \(c_k\) in \(L(K)\backslash L(H)\). Every loop in this set has an end in \(V(F)\). Therefore, as \(|V(F)|=2|F|\) it follows that \(o(\cH)\leq 2|F|\).

Proper extensions \[sec4070\] In this section the aim is to give necessary and sufficient conditions for a proper \(C\)-edge-coloured \(r\)-free-type graph of order \(n\) to have a proper extension.

\[def4080\] If \(vv=\lambda\in\Lambda\) then is the graph with vertex-set \(V(H\cdot\lambda)=V(H)\) and edge-set \(E(H\cdot\lambda)=E(H)\cup\{uv\,|\,u\in V\}\).

\[def4090\] If \(\eps=vw\in F\) then is the graph with vertex-set \(V(H\cdot\eps)=V(H)\) and edge-set \(E(H\cdot\eps)=E(H)\cup\{uv,uw\,|\,u\in V\}\cup\{vv,ww\}\).

\[ex4093\] Figure \[fig4095\] gives an example of \(H\cdot\lambda\) for a free-loop \(\lambda\) and \(H\cdot\eps\) for a free-edge \(\eps\).

\(H\), \(H\cdot\lambda\) and \(H\cdot\eps\)

\[def4100\] If \(\mu\in F\cup\Lambda\) then a -extension of a \(C\)-edge-coloured \(r\)-free-type graph \(\cH\) of order \(n\) is a \(C\)-edge-coloured \(r'\)-free-type graph \(\cJ=(H\cdot\mu,(C,\psi))\) of order \(n\) where \(r'=r+1\) if and only if \(\mu\in L\) and \(r'=r+2\) if and only if \(\mu\in F\).

\[def4110\] A loop-extension of \(\cH\) is a pair \((\lambda,\cJ)\), where \(\lambda\in\Lambda\) and \(\cJ\) is a \(\lambda\)-extension of \(\cH\). An edge-extension of \(\cH\) is a pair \((\eps,\cJ)\), where \(\eps\in F\) and \(\cJ\) is an \(\eps\)-extension of \(\cH\). An extension of \(\cH\) is a pair \((\mu,\cJ)\) where \(\mu\in F\cup\Lambda\) and \(\cJ\) is a \(\mu\)-extension of \(\cH\). An extension \((\mu,\cJ)\) is proper if and only if \(\cJ\) is proper.

The aim of this section is to give necessary and sufficient conditions for a proper \(C\)-edge-coloured \(r\)-free-type graph \(\cH\) of order \(n\) to have a proper extension. These conditions are given in terms of the existence of certain pairs. In the case of a loop-extension the pair consists of a set of colours \(S\) and a bijection between \(V\) and \(S\). In the case of an edge-extension each element of the pair corresponds to a vertex incident with the free edge and consists of a set of colours \(S\), a bijection and a colour which is to be used for a loop incident with the corresponding vertex.

If \(\cJ=(J,(C,\psi))\) is a proper \(\mu\)-extension of a proper \(C\)-edge-coloured \(r\)-free-type graph \(\cH\) of order \(n\) and \(w\in V(J)\) is an end of \(\mu\) then, by the definition of \(\mu\)-extension \(vw\in E(J)\) for every \(v\in V\). Therefore, as \(\cJ\) is proper, there are \(r\) distinct colours \(\psi(v_1w),\psi(v_2w),\ldots,\psi(v_rw)\) with the property that for every \(i\in [r]\) the colour \(\psi(v_iw)\) is missing at \(v_i\) in \(\cH\). Moreover, as \(\cJ\) is proper, \(\phi(\eps)\in C\backslash\{\psi(v_iw)\,|\,i\in [r]\}\).

\[def4120\] If \(S\subset C\) is a set of colours then \(\theta:V\rightarrow S\) is an -suitable map if and only if \(\theta\) is injective and \(\theta(v)\in M(v)\) for all \(v\in V\)

\[def4130\] A pair \((S,\theta)\) is -suitable if and only if \(S\subset C\), \(|S|=r\), \(c_k\notin S\) and \(\theta:V\rightarrow S\) is \(S\)-suitable.

It is easy to see that there is a correspondence between suitable pairs and loop extensions.

\[def4140\] If \(\cH=(H,(C,\phi))\) is a \(C\)-edge-coloured \(r\)-free-type graph of order \(n\) and \(vv=\lambda\in\Lambda\) then the -extension corresponding to a -suitable pair \((S,\theta)\) is the \(C\)-edge-coloured graph \(\cJ=(J,(C,\psi))\) where \(J=H\cdot\lambda\) and \(\psi\) is defined by \[\psi(e)= \left\lbrace \begin{array}{ccc} \phi(\eps) &\mbox{ if and only if } & e\in E(J)\cap E(H)\\ \theta(u) &\mbox{ if and only if } & e=uv\mbox{ for some } u\in V \end{array}\right.\]

\[ex4145\] If \(\cH\) is the \(C_{[8]}\)-edge-coloured \(4\)-free-type graph of order 8 in Figure \[fig4035\] and \(\lambda\) is the unique loop of colour \(c_6\) then \((S,\theta)\), where \(S=\{c_1,c_2,c_7,c_8\}\) and \(\theta:V\rightarrow S\) is given by \[\theta(v_1)=c_2,\theta(v_2)=c_8,\theta(v_3)=c_7,\theta(v_4)=c_1,\] is a \(\phi(\lambda)\)-suitable pair. Obviously \(S\subset C\), \(|S|=r=4\) and \(\phi(\lambda)=c_6\notin S\) so \((S,\theta)\) is \(\phi(\lambda)\)-suitable if and only if \(\theta\) is \(S\)-suitable. This follows because \(c_2\in M(v_1)\), \(c_8\in M(v_2)\), \(c_7\in M(v_3)\), \(c_1\in M(v_4)\) and because \(\theta(v_i)=\theta(v_j)\) implies \(i=j\).

\[lem4150\] If \(\cH\) is a \(C\)-edge-coloured \(r\)-free-type graph of order \(n\) then the \(\lambda\)-extension corresponding to a \(\phi(\lambda)\)-suitable pair is a uniquely defined \(\lambda\)-extension of \(\cH\).

If \(\cJ=(J,(C,\psi))\) is the \(\lambda\)-extension corresponding to the \(\phi(\lambda)\)-suitable pair \((S,\theta)\) then \(\cJ\) is a \(\lambda\)-extension because \(J=H\cdot\lambda\), by definition and, from the definition of \(\psi\), \(\cH\) is embedded in \(\cJ\). The uniqueness follows because \(J\) is uniquely defined and \(\psi\) is well-defined.

\[def4160\] If \(\cH=(H,(C,\phi))\) is a proper \(C\)-edge-coloured \(r\)-free-type graph of order \(n\) and \((v,vv)=\lambda\in\Lambda\) then the pair corresponding a -extension \(\cJ=(J,(C,\psi))\) of \(\cH\) is the pair \((S,\theta)\) where \(S=\{c\in C\,|\,\psi(uv)=c\mbox{ for some }u\in V\}\) and \(\theta:V\rightarrow S\) is defined by \(\theta(u)=\psi(uv)\) for all \(u\in V\).

\[ex4164\] If \(\cH\) is the \(C_{[8]}\)-edge-coloured \(4\)-free-type graph of order \(8\) in Figure \[fig4035\], \(\lambda\) is the unique free-loop of colour \(c_6\) in \(\cH\) and \(\cJ\) is the \(\lambda\)-extension of \(\cH\) in Figure \[fig4166\] then the corresponding pair is \((S,\theta)\) where \(S=\{c_1,c_2,c_7,c_8\}\) and \(\theta:V\rightarrow S\) is defined by \(\theta(v_1)=c_2\), \(\theta(v_2)=c_8\), \(\theta(v_3)=c_7\) and \(\theta(v_4)=c_1\).

The question now is which suitable pairs correspond to proper extensions. The answer, proved in Lemma \[lem4180\], is that being suitable is both necessary and sufficient for the corresponding extension to be proper.

A proper \(\lambda\)-extension

\[def4170\] If \(\cH=(H,(C,\phi))\) is a proper \(C\)-edge-coloured \(r\)-free-type graph of order \(n\) and \(\lambda\in\Lambda\) then a \(\phi(\lambda)\)-suitable pair \(\cS=(S,\theta)\) is -proper if and only if the \(\lambda\)-extension corresponding to \((S,\theta)\) is proper.

\[exam4175\] If \(\cH\) is the \(C_{[8]}\)-edge-coloured \(4\)-free-type graph of order \(8\) in Figure \[fig4035\], \(\lambda\) is the unique free-loop of colour \(c_6\) in \(\cH\) and \(\cJ\) is the \(\lambda\)-extension of \(\cH\) in Figure \[fig4166\] then the corresponding pair \((S,\theta)\) is \(\phi(\lambda)\)-proper because \(\cJ\) is proper.

\[lem4180\] If \(\cH=(H,(C,\phi))\) is a proper \(C\)-edge-coloured \(r\)-free-type graph of order \(n\) and \(\lambda\in\Lambda\) then a pair \((S,\theta)\) is \(\phi(\lambda)\)-proper if and only if \((S,\theta)\) is \(\phi(\lambda)\)-suitable.

Let \(\cJ\) be the \(\lambda\)-extension of \(\cH\) corresponding to the \(\phi(\lambda)\)-suitable pair \((S,\theta)\). By definition, \((S,\theta)\) is \(\phi(\lambda)\)-proper if and only if \(\cJ\) is proper.

Let \(\{e,e'\}\subseteq E(J)\) be a pair of edges of \(J\) with a common end. If \(\{e,e'\}\subseteq E(J)\cap E(H)\) and \(e\neq e'\) then, by definition, \(\psi(e)=\phi(e)\) and \(\psi(e')=\phi(e)\). As \(\cH\) is proper \(\phi(e)\neq\phi(e')\). Therefore \(\psi(e)\neq\psi(e')\). If \(\{e,e'\}\subseteq E(J)\backslash E(H)\) then \(e=uv\) for some \(u\in V\) and \(e'=u'v\) for some \(u'\in V\), where \(v\) is the end of \(\lambda\). Therefore, by definiton, \(\psi(e)=\theta(u)\) and \(\psi(e')=\theta(u')\). Hence, as \(\theta\) is injective, it follows that \(u=u'\) and, consequently, \(e=e'\).

Otherwise, without loss of generality, suppose that \(e\in E(J)\cap E(H)\) and \(e'\in E(J)\backslash E(H)\). As \(e'\in E(J)\backslash E(H)\) it follows that \(e'=uv\) for some \(u\in V\), where \(v\) is the end of \(\lambda\), and, consequently, by definition, \(\psi(e')=\theta(u)\). As \(e\) and \(e'\) have a common end and \(e\in E(J)\cap E(H)\) it follows that either \(e=uw\) for some \(w\in V\) (where \(w=u\) is possible) or \(e=vv\). If \(e=uw\) then \(\psi(e)=\phi(e)\) and because \(\theta(u)\in M(u)\) it follows that \(\theta(u)\neq\phi(e)\) and therefore that \(\psi(e')\neq\psi(e)\). Finally, if \(e=vv\) then \(\psi(e)=\phi(\lambda)\) and therefore as \(\phi(\lambda)\notin S\) and \(\psi(e')=\theta(u)\in S\) it follows that \(\psi(e)\neq\psi(e')\).

Much as in Chapter 2 a pair of suitable pairs is required for an edge-extension. However, unlike in Chapter 2, this time a pair of colours for the loops adjoined to the free-edge is also needed.

\[def4190\] If \(\cH=(H,(C,\phi))\) is a \(C\)-edge-coloured \(r\)-free-type graph and \(\eps\in F\) then a pair \(\{(S,\theta_S,c_s),(T,\theta_T,c_t)\}\) is -suitable if and only if both \((S,\theta_S)\) and \((T,\theta_T)\) are \(\phi(\eps)\)-suitable and \(\{c_s,c_t\}\subset C\).

\[def4200\] If \(\cH=(H,(C,\phi))\) is a \(C\)-edge-coloured \(r\)-free-type graph of order \(n\) and \(vw=\eps\in F\) then the -extension corresponding to a -suitable pair \(\{(S,\theta_S,c_s),(T,\theta_T,c_t)\}\) is the \(\eps\)-extension \(\cJ=(J,(C,\psi))\) defined by \(J=H\cdot\eps\) and \[\psi(e)=\left\lbrace \begin{array}{ccc} \phi(e) & \mbox{ if and only if } & e\in E(J)\cap E(H) \\ \theta_S(u) & \mbox{ if and only if } & e=uv\mbox{ for some } u\in V \\ \theta_T(u) & \mbox{ if and only if } & e=uw\mbox{ for some } u\in V \\ c_s & \mbox{ if and only if } & e=vv \\ c_t & \mbox{ if and only if } & e=ww \end{array} \right.\]

\[ex4204\] If \(\cH\) is the \(C_{[8]}\)-edge-coloured \(3\)-free-type graph of order \(8\) in Figure \[fig4205\], \(S=\{c_4,c_6,c_6\}\), \(T=\{c_2,c_7,c_8\}\), \(c_s=c_3\), \(c_t=c_6\) and \(\theta_S\) and \(\theta_T\) are defined by \[\theta_S(v_1)=c_7,\theta_S(v_2)=c_6,\theta_S(v_3)=c_4\] \[\theta_T(v_1)=c_2,\theta_T(v_2)=c_8,\theta_T(v_3)=c_7\] then \(\{(S,\theta_S,c_s),(T,\theta_T,c_t)\}\) is a \((\phi(\eps),c_s,c_t)\)-suitable pair. The corresponding \(\eps\)-extension is the \(C_{[8]}\)-edge-coloured \(5\)-free-type graph of order \(8\) in Figure \[fig4166\].

A \(C_{[8]}\)-edge-coloured \(3\)-free-type graph of order \(8\)

\[lem4206\] If \(\cH\) is a \(C\)-edge-coloured \(r\)-free-type graph of order \(n\) and \(\eps\in F\) then the \(\eps\)-extension corresponding to an \((\phi(\eps),c_s,c_t)\)-suitable pair is a uniquely defined \(\eps\)-extension of \(\cH\)

Suppose that \(vw=\eps\in F\) and \(\{(S,\theta_S,c_s),(T,\theta_T,c_t)\}\) is a \((\phi(\eps),c_s,c_t)\)-suitable pair with corresponding \(\eps\)-extension \(\cJ=(J,(C,\psi))\). Then, by definition, \(J=H\cdot\eps\) and, from the definition of \(\psi\), \(\cH\) is embedded in \(\cJ\). The uniqueness of \(\cJ\) follows from the obvious uniqueness of \(J\), \(c_s\) and \(c_t\) and because \(\theta_S\) and \(\theta_T\) are well-defined.

\[def4210\] If \((\{v,w\},vw)=\eps\in F\) then the pair corresponding to a proper -extension \(\cJ=(J,(C,\psi))\) of \(\cH\) is the pair \(\{(S,\theta_s,c_s),(T,\theta_t,c_t)\}\), where \[S=\{c_k\in C\,|\,\psi(uv)=c_k\mbox{ for some } u\in V\},\] \[T=\{c_k\in C\,|\,\psi(uw)=c_k\mbox{ for some } u\in V\},\] \(c_s=\psi(vv)\), \(c_t=\psi(ww)\) and \(\theta_s:V\rightarrow S\), \(\theta_s:V\rightarrow T\) are defined by \(\theta_s(u)=\psi(uv)\) and \(\theta_t(u)=\psi(uw)\) for all \(u\in V\).

\[ex4212\] If \(\cH\) is the \(C_{[8]}\)-edge-coloured \(3\)-free-type graph of order \(8\) in Figure \[fig4205\] and \(\cJ\) is the \(\eps\)-extension in Figure \[fig4166\] then the pair corresponding to \(\cJ\) is \(\{(S,\theta_S,c_s),(T,\theta_T,c_t)\}\) where \(S=\{c_4,c_6,c_6\}\), \(T=\{c_2,c_7,c_8\}\), \(c_s=c_3\), \(c_t=c_6\) and \(\theta_S\) and \(\theta_T\) are defined by \[\theta_S(v_1)=c_7,\theta_S(v_2)=c_6,\theta_S(v_3)=c_4\] \[\theta_T(v_1)=c_2,\theta_T(v_2)=c_8,\theta_T(v_3)=c_7\]

\[lem4215\] If \(\cH\) is a \(C\)-edge-coloured \(r\)-free-type graph and \((\{v,w\},vw)=\eps\in F\) then the pair corresponding to a proper \(\eps\)-extension \(\cJ=(J,(C,\psi))\) of \(\cH\) is a uniquely defined \((\phi(\eps),c_s,c_t)\)-proper pair, where \(c_s=\psi(vv)\) and \(c_t=\psi(ww)\).

Let \(\{(S,\theta_S,c_s),(T,\theta_T,c_t)\}\) be the pair corresponding to \(\cJ\). Firstly \(\theta_S\) is \(S\)-suitable because \(\theta_S(u)=\psi(uv)\) for all \(u\in V\) and, because \(\cJ\) is proper it follows that \(\psi(uv)\in M(\cJ,u)\) for all \(u\in V\). By a similar argument it follows that \(\theta_T\) is \(T\)-proper. It is obvious that \(|S|=|V|=r\). \(\phi(\eps)\notin S\) follows because \(\cJ\) is proper and therefore, because \(v\in V(J)\backslash V\) is an end of \(\eps\), \(\psi(uv)\neq\phi(\eps)\) for all \(u\in V\). By a similar argument \(\phi(\eps)\notin T\), therefore \(\phi(\eps)\in C\backslash (S\cup T)\). Also because \(\cJ\) is proper it follows that \(c_s\in C\backslash (S\cup\{\phi(\eps)\})\), \(c_t\in C\backslash (T\cup\{\phi(\eps)\})\) and \(\theta_S(u)\neq\theta_T(u)\) for all \(u\in V\). Therefore \(\{(S,\theta_S,c_s),(T,\theta_T,c_t)\}\) is \((\phi(\eps),c_s,c_t)\)-proper.

Once again the pairs of most interest are those whose corresponding extension is proper.

\[def4220\] If \(\eps\in F\) then a \((\phi(\eps),c_s,c_t)\)-suitable pair is a -proper pair if and only if the corresponding \(\eps\)-extension is proper.

\[lem4230\] If \(\eps\in F\) then a \((\phi(\eps),c_s,c_t)\)-suitable pair \(\{(S,\theta_S,c_s),(T,\theta_T,c_t)\}\) is \((\phi(\eps),c_s,c_t)\)-proper if and only if \(\phi(\eps)\in C\backslash (S\cup T)\), \(c_s\in C\backslash(S\cup\{\phi(\eps)\})\), \(c_t\in C\backslash(T\cup\{\phi(\eps)\})\) and \(\theta_S(u)\neq\theta_T(u)\) for all \(u\in V\).

Let \(\cJ\) be the \(\eps\)-extension corresponding to the \((\phi(\eps),c_s,c_t)\)-suitable pair \(\{(S,\theta_S,c_s),(T,\theta_T,c_t)\}\). Then, by definition, \(\{(S,\theta_S,c_s),(T,\theta_T,c_t)\}\) is \((\phi(\eps),c_s,c_t)\)-proper if and only if \(\cJ\) is proper.

Suppose that \(\cJ\) is proper. By definition \(\psi(\eps)=\phi(\eps)\). Therefore, as \(S\cup T=\{c_k\in C\,|\,\psi(uv)=c_k\mbox{ for some }u\in V\mbox{ and }v\mbox{ an end of }\eps\}\) and \(\cJ\) is proper \(C\)-edge-coloured, it follows that \(\psi(\eps)\in C\backslash (S\cup T)\). If \(\eps=vw\) then \(S=\{c_k\in C\,|\,\psi(uv)=c_k\mbox{ for some }u\in V\}\) and \(T=\{c_k\in C\,|\,\psi(uw)=c_k\mbox{ for some }u\in V\}\). Therefore, as \(c_s=\psi(vv)\) and \(c_t=\psi(ww)\) it follows that \(c_s\in C\backslash(S\cup\{\phi(\eps)\})\) and \(c_t\in C\backslash(T\cup\{\phi(\eps)\})\). Finally, as \(\cJ\) is proper, \(\theta_S(u)=\psi(uv)\neq\psi(uw)=\theta_T(u)\) for all \(u\in V\).

Now suppose that \(\{(S,\theta_S,c_s),(T,\theta_T,c_t)\}\) satisfies the conditions of the lemma and that \(\cJ\) is the \(\eps\)-extension corresponding to the \((\phi(\eps),c_s,c_t)\)-suitable pair \(\{(S,\theta_S,c_s),(T,\theta_T,c_t)\}\). Let \(\{e,e'\}\subset E(J)\) be two edges with a common end. If \(\{e,e'\}\subseteq E(J)\cap E(H)\) then, by definition, \(\psi(e)=\phi(e)\) and \(\psi(e')=\phi(e')\). Therefore, if \(e\neq e'\), it follows, as \(\cH\) is proper, that \(\phi(e)\neq\phi(e')\) and hence that \(\psi(e)\neq\psi(e')\).

If \(\{e,e'\}\subseteq E(J)\backslash E(H)\) then either \(e=uv\) and \(e'=uw\) for some \(u\in V\), where \(\eps=vw\) or \(e=uv\) for some \(u\in V\) and \(e'=vv\), where \(v\) is an end of \(\eps\). In the first case, by definition, \(\psi(e)=\theta_S(u)\) and \(\psi(e')=\theta_T(u)\). Therefore, as \(\theta_S(u)\neq\theta_T(u)\), it follows that \(\psi(e)\neq\psi(e')\). In the second case, without loss of generality, \(\psi(e)=\theta_S(u)\) for some \(u\in V\) and \(\psi(e')=c_s\). Because \(\theta_S\) is an \(S\)-map \(\theta_S(u)\in S\) and, by definition, \(c_s\in C\backslash (S\cup\{\phi(e)\})\) it follows that \(\theta_S(u)\neq c_s\) and therefore \(\psi(e')\neq\psi(e)\).

Otherwise, without loss of generality, suppose \(e\in E(J)\cap E(H)\) and \(e'\in E(J)\backslash E(H)\). Then either \(e'=uv\) for some \(u\in V\) or \(e'=vv\), where \(v\) is an end of \(\eps\).

If \(e'=uv\) then either \(e=\eps\) or \(e=uu'\) for some \(u'\in V\). If \(e=\eps\) then \(\psi(e)=\phi(e)=\phi(\eps)\) and therefore, as \(\psi(e')=\theta_S(u)\), \(\phi(\eps)\in C\backslash S\) and \(\theta_S\) is an \(S\)-map it follows that \(\theta_S(u)\neq\phi(\eps)\) and hence \(\psi(e)\neq\psi(e')\). Otherwise \(e=uu'\) and then \(\psi(e)=\phi(e)\) and \(\psi(e')=\theta_S(u)\in M(u)\) therefore \(\theta_S(u)\neq\phi(e)\) and so \(\psi(e)\neq\psi(e')\).

If, on the other hand, \(e'=vv\) then either \(e=uv\) or \(e=\eps\). If \(e=uv\) then \(\psi(e)=\theta_S(u)\in S\) and therefore, as \(\psi(e')=c_s\notin S\) it follows that \(\theta_S(u)\neq c_s\) and hence \(\psi(e)\neq\psi(e')\). Finally, if \(e=\eps\) then \(\psi(\eps)=\phi(\eps)\) and therefore, as \(c_s\in C\backslash\{\phi(\eps)\}\) it follows that \(c_s\neq\phi(\eps)\) and hence \(\psi(e')\neq\psi(e)\).

Ryser extensions \[sec4250\] In this section the aim is to extend the characterisation of proper extensions in the previous section to give necessary and sufficient conditions for a Ryser proper \(C\)-edge-coloured \(r\)-free-type graph to have a Ryser \(\mu\)-extension for all \(\mu\in F\cup\Lambda\). Much as in Chapter 2 there are certain critical and semi-critical colours \(c_k\in C\) and an extension is Ryser provided these colours are used frequently enough on edges of \(E(J)\backslash E(H)\).

\[def4270\] If \(\cH\) is a \(C\)-edge-coloured \(r\)-free-type graph of order \(n\) then \(\xk=\xrk=2\ek+\lk-((2r-n)+2\Ek+\Lk)\) for all \(c_k\in C\).

\[def4320\] A colour \(c_k\in C\) is critical if and only if \(\xk\in\{0,1\}\) and \(c_k\in C\) is semi-critical if and only if \(\xk\in\{2,3\}\)

In Lemma \[lem4330\] it is proved that if \(\lambda\in\Lambda\) then a \(\lambda\)-extension \(\cJ\) is Ryser if and only if every critical colour, apart from \(\phi(\lambda)\), appears on some edge of \(E(J)\backslash E(H)\). In Lemma \[lem4350\] it is proved that if \(\eps\in F\) then an \(\eps\)-extension is Ryser if and only if every critical colour, apart from \(\phi(\eps)\), \(c_s\) and \(c_t\), appears twice and every semi-critical colour, apart from \(\phi(\eps)\), \(c_s\) and \(c_t\), appears at least once on edges of \(E(J)\backslash E(H)\). and moreover the colours \(c_s\) and \(c_t\) satisfy a further two conditions then \(\cJ\) is Ryser.

Before Lemma \[lem4330\] and Lemma \[lem4350\] are proved three other results, Lemma \[lem4280\], Lemma \[lem4290\] and Lemma \[lem4295\] are proved. These lemmas are little more than observations which make the proofs of Lemma \[lem4330\], Lemma \[lem4350\] and others beside slighty less tedious. Lemma \[lem4280\], Lemma \[lem4290\] and Lemma \[lem4295\] all involve the notation introduced in the next definition.

\[def4260\] If \(\cH\) is a proper \(C\)-edge-coloured \(r\)-free-type graph, \(\mu\in F\cup\Lambda\) and \(\cJ\) is a \(\mu\)-extension of \(\cH\) then, for all \(f\in\{e,l,\eps,\lambda\}\), \(\fdk=\frkk-\frk\) for all \(c_k\in C\).

\[lem4280\] If \(\cH\) is a proper \(C\)-edge-coloured \(r\)-free-type graph and \(\mu\in F\cup\Lambda\) then a \(\mu\)-extension \(\cJ\) of \(\cH\) is Ryser if and only if (\[lem42801\]) holds for every \(c_k\in C\).

1. \[lem42801\] \(2\edk+\ldk\geq 2(r'-r)+2\Edk+\Ldk-\xk\)

By definition \(\cJ\) is Ryser if and only if (\[eqn4300\]) is satisfied by every \(c_k\in C\).\[\label{eqn4300} 2\erkk+\lrkk\geq 2r'-n+2\Erkk+\Lrkk\] From the definition of \(\xk\), (\[eqn4310\]) is satisfied by every \(c_k\in C\). \[\label{eqn4310} 2\ek+\lk=2r-n+2\Ek+\Lk+\xk\] Now, as \(\cH\) is embedded in \(\cJ\) we can interpret (\[eqn4310\]) as a statement about \(\cH\) as an edge-coloured subgraph of \(\cJ\) and legitimately subtract (\[eqn4310\]) from (\[eqn4300\]) to give (\[lem42801\]). It follows that (\[eqn4300\]) holds if and only if (\[lem42801\]) holds. Therefore \(\cJ\) is Ryser if and only if (\[lem42801\]) holds for all \(c_k\in C\).

\[lem4290\] If \(\cH\) is a proper \(C\)-edge-coloured \(r\)-free-type graph, \(\lambda\in\Lambda\) and \(\cJ\) is a proper \(\lambda\)-extension of \(\cH\) then \(\edk\in\{0,1\}\), \(\ldk=\Ldk=\Edk=0\) if \(c_k\in C\backslash\{\phi(\lambda)\}\) and \(\edk=\Edk=0\), \(\ldk=1\) and \(\Ldk=-1\) if \(c_k=\phi(\lambda)\).

As \(\cH\) is embedded in \(\cJ\) it follows that every edge of colour \(c_k\) in \(\cH\) is an edge of colour \(c_k\) in \(\cK\). Therefore \(\fdk\geq 0\) for all \(f\in\{e,\eps,l,\lambda\}\) and \(c_k\in C\). If \(e\in E(J)\backslash E(H)\) then \(e=uv\) for some \(u\in V\) and end \(v\) of \(\lambda\). Therefore, as \(\cJ\) is proper, it follows that \(\edk\leq 1\). If \(c_k\in C\backslash\{\phi(\lambda)\}\) then, as every loop of colour \(c_k\) in \(\cJ\) is a loop of colour \(c_k\) of \(\cH\) it follows that \(\ldk=\Ldk=0\). Because every free-edge of \(J\) is a free-edge of \(H\) it follows that \(\Edk=0\) for all \(c_k\in C\). Finally, if \(c_k=\phi(\lambda)\) then \(\cJ\) has exactly one more loop, namely \(\lambda\), of colour \(c_k\) than \(\cH\). Therefore \(\ldk=1\) and, as \(\lambda\) was a free loop of colour \(c_k\) of \(\cH\), \(\Ldk=-1\).

\[lem4295\] If \(\cH\) is a proper \(C\)-edge-coloured \(r\)-free-type graph, \(\eps\in F\) and \(\cJ\) is a proper \(\eps\)-extension of \(\cH\) then (\[lem42951\])-(\[lem42954\]) hold.

1. \(\edk\in\{0,1,2\}\), \(\ldk=\Ldk=\Edk=0\) if \(c_k\in C\backslash\{\phi(\eps),c_s,c_t\}\)\[lem42951\]

2. \(\edk=1\), \(\ldk=\Ldk=-1\) and \(\Edk=-1\) if \(c_k=\phi(\eps)\)\[lem42952\]

3. \(\edk\in\{0,1\}\), \(\ldk=1\) and \(\Ldk=\Edk=0\) if \(c_s\neq c_t\) and \(c_k\in\{c_s,c_t\}\)\[lem42953\]

4. \(\edk=\Ldk=\Edk=0\) and \(\ldk=2\) if \(c_k=c_s=c_t\)\[lem42954\]

As \(\cH\) is embedded in \(\cJ\) it follows that every edge of colour \(c_k\) in \(\cH\) is an edge of colour \(c_k\) in \(\cJ\). Therefore \(\fdk\geq 0\) for all \(f\in\{e,\eps,l,\lambda\}\) and \(c_k\in C\).

Because a loop \(\lambda\) is a free loop of \(H\) if and only if \(\lambda\) is a free-loop of \(J\) it follows that \(\Ldk=0\) for all \(c_k\in C\).

As \(\cJ\) is an \(\eps\)-extension it follows that \(\Edk=-1\) if and only if \(c_k=\phi(\eps)\) and \(\Edk=0\) for all \(c_k\in C\backslash\{\phi(\eps)\}\).

Also as \(c_s\) and \(c_t\) are the colours of loops in \(E(J)\backslash E(H)\) it follows that \(\ldk=1\) if and only if \(c_s\neq c_t\) and \(c_k\in\{c_s,c_t\}\), \(\ldk=2\) if and only if \(c_k=c_s=c_t\) and \(\ldk=0\) for all \(c_k\in C\backslash\{c_s,c_t\}\).

\[lem4320\] If \(\lambda\in\Lambda\) and \((S,\theta)\) and \(\cJ\) are corresponding \(\phi(\lambda)\)-suitable pair and \(\lambda\)-extension then \(c_k\in S\) if and only if \(\edk=1\).

By definition \(c_k\in S\) if and only if \(\psi(vw)=c_k\) for some \(v\in V\) and end \(w\) of \(\lambda\). Therefore \(c_k\in S\) if and only if \(\edk\geq 1\). The result follows because \(\edk\leq 1\).

\[def4325\] If \(\lambda\in\Lambda\) then a \(\lambda\)-proper pair \((S,\theta)\) is Ryser if and only the corresponding \(\lambda\)-extension is Ryser.

\[lem4330\] If \(\lambda\in\Lambda\) and \((S,\theta)\) is a \(\lambda\)-proper pair then \((S,\theta)\) is Ryser if and only if \(S\) contains every critical colour \(c_k\in C\backslash\{\phi(\eps)\}\).

Let \(\cJ\) be the \(\lambda\)-proper extension of \(\cH\) corresponding to \((S,\theta)\). By definition \((S,\theta)\) is Ryser if and only if \(\cJ\) is Ryser and by Lemma \[lem4280\], \(\cJ\) is Ryser if and only if Lemma \[lem4280\] (\[lem42801\]) is satisfied by every \(c_k\in C\).

Now, if \(c_k\in C\backslash\{\phi(\lambda)\}\) then, by Lemma \[lem4290\], \(\ldk=\Ldk=\Edk=0\). Therefore, as \(r'=r+1\), it follows from Lemma \[lem4280\] that \(\cH\) is Ryser if an only if (\[eqn4340\]) is satisfied. \[\label{eqn4340} 2\edk\geq 2-\xk\] If \(\xk\geq 2\) then this condition is trivial because \(\edk\) is non-negative by definition. Otherwise, as \(\cH\) is Ryser, \(c_k\) is critical and (\[eqn4340\]) holds if and only if \(\edk\geq 1\). In the case of a loop-extension \(\edk\leq 1\) so (\[eqn4340\]) holds if and only if \(\edk=1\). From Lemma \[lem4320\], \(\edk=1\) if and only if \(c_k\in S\).

If \(c_k=\phi(\lambda)\) then, by Lemma \[lem4290\], \(\ldk=1\), \(\Ldk=-1\) and \(\Edk=\edk=0\). Consequently, by Lemma \[lem4280\], \(\cH\) is Ryser.

\[def4345\] If \(\eps\in F\) then a \((\phi(\eps),c_s,c_t)\)-proper pair \(\{(S,\theta_s,c_s),(T,\theta_t,c_t)\}\) is Ryser if and only if the corresponding \(\eps\)-extension is Ryser.

\[lem4357\] If \(\eps\in F\) and \(\{(S,\theta_S,c_s),(T,\theta_T,c_t)\}\) and \(\cJ\) aree corresponding \((\phi(\eps),c_s,c_t)\)-proper pair and \((\phi(\eps),c_s,c_t)\)-proper extension then \(\edk=2\) if and only if \(c_k\in S\cap T\), \(\edk\geq 1\) if and only if \(c_k\in S\cup T\) and \(\edk=0\) if and only if \(c_k\in C\backslash (S\cup T)\).

By definition \(c_k\in S\) if and only if \(\psi(uv)=c_k\) for some \(u\in V\) and \(c_k\in T\) if and only if \(\psi(uw)=c_k\) for some \(u\in V\), where \(v\) and \(w\) are the ends of \(\eps\). Therefore, as \(\edk\leq 2\), it follows that \(\edk=2\) if and only if \(c_k\in S\cap T\), \(\edk\geq 1\) if and only if \(c_k\in S\cup T\) and \(\edk=0\) if and only if \(c_k\in C\backslash (S\cup T)\).

\[lem4350\] If \(\eps\in F\) and \(\{(S,\theta_s,c_s),(T,\theta_t,c_t)\}\) is \((\phi(\eps),c_s,c_t)\)-proper then \(\{(S,\theta_s,c_s),(T,\theta_t,c_t)\}\) is Ryser if and only if (\[lem43501\])-(\[lem43503\]) hold.

1. \[lem43501\] If \(c_k\in C\backslash\{\phi(\eps),c_s,c_t\}\) is critical then \(c_k\in S\cap T\) and if \(c_k\in C\backslash\{\phi(\eps),c_s,c_t\}\) is semi-critical then \(c_k\in S\cup T\).

2. \[lem43502\] If \(c_s\neq c_t\) and \(c_k\in\{c_s,c_t\}\) then \(\xk>0\) and, if \(\xk\in\{1,2\}\) then \(c_k\in S\cup T\) .

3. \[lem43503\] If \(c_k=c_s=c_t\) then \(\xk\geq 2\).

By definition \(\{(S,\theta_s,c_s),(T,\theta_t,c_t)\}\) is Ryser if and only if the \(\eps\)-extension \(\cJ\) corresponding to the \(\phi(\eps)\)-suitable pair \(\{(S,\theta_s,c_s),(T,\theta_t,c_t)\}\) is Ryser.

Suppose that \(c_k\in C\backslash\{\phi(\eps),c_s,c_t\}\). From Lemma \[lem4295\] \(\Ldk=\Edk=\ldk=0\). It follows, from Lemma \[lem4280\] that \(\cJ\) is Ryser if and only if (\[eqn4360\]) holds. \[\label{eqn4360} 2\edk\geq 4-\xk\] If \(\xk\geq 4\) then (\[eqn4360\]) holds because \(\edk\geq 0\). If \(c_k\) is semi-critical then (\[eqn4360\]) holds if and only if \(\edk\geq 1\) and if \(c_k\) is critical then (\[eqn4360\]) holds if and only if \(\edk\geq 2\). Now (\[lem43501\]) follows from Lemma \[lem4357\] because \(\edk\geq 1\) if and only if \(c_k\in S\cup T\) and \(\edk= 2\) if and only if \(c_k\in S\cap T\).

If \(c_k\in\{c_s,c_t\}\) and \(c_s\neq c_t\) then, by Lemma \[lem4295\], \(\Edk=\Ldk=0\), \(\ldk=1\) and \(\edk\leq 1\). Therefore (\[lem43503\]) holds if and only if \(2\edk\geq 3-\xk\) and, because \(\edk\leq 1\), it follows that \(\xk\geq 1\). If \(\xk\geq 3\) then this condition is trivial because \(\edk\geq 0\). If \(\xk\in\{1,2\}\) then this condition holds if and only if \(\edk\geq 1\) which, from Lemma \[lem4357\], holds if and only if \(c_k\in S\cup T\).

If \(c_k\in\{c_s,c_t\}\) and \(c_s=c_t\) then, by Lemma \[lem4295\], \(\Edk=\Ldk=\edk=0\) and \(\ldk=2\). Therefore (\[eqn4360\]) holds if and only if \(x(c_k)\geq 2\).

Finally, if \(c_k=\phi(\eps)\) then, by Lemma \[lem4295\], \(\Edk=-1\), \(\edk=1\) and \(\ldk=\Ldk=0\). Therefore (\[lem43503\]) holds because \(\cH\) is Ryser and hence \(\xk\geq 0\).

Admissible extensions \[sec4370\] Generally, a Ryser extension is not admissible. In this section necessary and sufficient condition for an extension to be admissible are given. In fact, in the case of a loop-extension, as shown in Lemma \[lem4380\], the condition is vacuous.

\[def4390\] If \(\lambda\in\Lambda\) and \((S,\theta)\) is \(\phi(\lambda)\)-proper then \((S,\theta)\) is admissible if and only if the \(\lambda\)-extension corresponding to \((S,\theta)\) is admissible.

\[lem4380\] If \(\cH\) is an admissible proper \(C\)-edge-coloured \(r\)-free-type graph of order \(n\), \(\lambda\in\Lambda\) and \(\cJ\) is a \(\lambda\)-extension of \(\cH\) then \(\cJ\) is admissible.

From Lemma \[lem4290\] it follows that if \(c_k=\phi(\lambda)\) then \(\ldk=1\) and \(\Ldk=-1\) and if \(c_k\in C\backslash\{\phi(\lambda)\}\) then \(\ldk=\Ldk=0\). Therefore \(\lrkk+\Lrkk=\lk+\Lk\) for all \(c_k\in C\). It follows that \(O(\cJ)=O(\cH)\) and, as \(\cH\) is admissible, that \(\lrkk+\Lrkk\leq 1\) for all \(c_k\in C\). Therefore \(\cJ\) is admissible if \(n\) is odd. If \(n\) is even, as \(\cH\) is admissible and \(F(J)=F(H)\), it follows that \(o(\cJ)=o(\cH)=2|F(\cJ)|=2|F(\cH)|\). Hence \(\cJ\) is admissible.

\[cor4400\] If \(\cH\) is an admissible proper \(C\)-edge-coloured \(r\)-free-type graph of order \(n\), \(\lambda\in\Lambda\) and \((S,\theta)\) is a \(\phi(\lambda)\)-proper pair then \((S,\theta)\) is admissible.

In the case of an edge-extension matters are complicated slightly because of the fact that two new loops are introduced.

\[def4410\] If \(\eps\in F\) and \(\{(S,\theta_S,c_s),(T,\theta_T,c_t)\}\) is \((\phi(\eps),c_s,c_t)\)-proper then \(\{(S,\theta_S,c_s),(T,\theta_T,c_t)\}\) is admissible if and only if the \(\eps\)-extension corresponding to \(\{(S,\theta_S,c_s),(T,\theta_T,c_t)\}\) is admissible.

Intuitively it seems reasonable that if \(n\) is odd then an edge-extension is admissible provided that the colours \(c_s,c_t\) used on the loops adjoined to the free-edge are distinct and used on no other loop. In this case the intution is correct and this is proved in Lemma \[lem4430\]. If \(n\) is even the condition is slightly more complicated. If \(o(\cH)\leq 2|F|-4\) then the condition is vacuous. If \(o(\cH)\in\{2|F|-2,2|F|-3\}\) then it is required that either \(c_s=c_t\) or at least one of \(c_s,c_t\) is an element of \(O(\cH)\). Otherwise \(c_s\) and \(c_t\) must be distinct and both elements of \(O(\cH)\).

\[def4420\] A pair of colours \(\{c_s,c_t\}\subset C\backslash\{\phi(\eps)\}\) are a -admissible pair of colours if and only if \(n\) is odd and (\[lem44201\]) holds or \(n\) is even and (\[lem44202\]) holds.

1. \(c_s\neq c_t\) and \(l(c_s)=\lambda(c_s)=l(c_t)=\lambda(c_t)=0\) \[lem44201\]

2. either (\[lem442021\]), (\[lem442022\]) or (\[lem442023\]) holds \[lem44202\]

   1. \(o(\cH)\leq 2|F|-4\) \[lem442021\]

   2. \(o(\cH)\in\{2|F|-2,2|F|-3\}\) and either \(c_s=c_t\) or \(c_s\neq c_t\) and \(|\{c_s,c_t\}\cap O(\cH)|=1\) \[lem442022\]

   3. \(c_s\neq c_t\) and \(\{c_s,c_t\}\subset O(\cH)\) \[lem442023\]

\[lem4430\] If \(\eps\in F\) and \(\{(S,\theta_S,c_s),(T,\theta_T,c_t)\}\) is \((\phi(\eps),c_s,c_t)\)-proper then \(\{(S,\theta_S,c_s),(T,\theta_T,c_t)\}\) is admissible if and only if \(\{c_s,c_t\}\) are a \(\phi(\eps)\)-admissible pair of colours.

By definition \(\{(S,\theta_S,c_s),(T,\theta_T,c_t)\}\) is admissible if and only if the corresponding \(\eps\)-extension \(\cJ=(J,(C,\psi))\) is admissible.

If \(n\) is odd then, by definition, \((\eps,\cJ)\) is admissible if and only if \(\lrkk+\Lrkk\leq 1\) holds for all \(c_k\in C\). As \((\eps,\cJ)\) is an edge-extension of \(\cH\) it follows, from Lemma \[lem4295\], that \(\lrkk+\Lrkk=\lk+\Lk\) for all \(c_k\in C\backslash\{c_s,c_t\}\). Therefore, as \(\cH\) is admissible, it follows that \(\lrkk+\Lrkk\leq 1\) for all \(c_k\in C\backslash\{c_s,c_t\}\).

If \(c_k\in\{c_s,c_t\}\) then, from Lemma \[lem4295\], it follows that \(\lrkk\geq\lk+1\). Therefore \(\lrkk+\Lrkk\leq 1\) if and only if \(\lrkk=\lk+1\) and \(\lk=\Lk=0\). Now \(\lrkk=\lk+1\) and \(\lk+\Lk=0\) if and only if \(c_s\neq c_t\) and \(l(c_s)=\lambda(c_s)=l(c_t)=\lambda(c_t)=0\).

Now suppose that \(n\) is even. By definition \((\eps,\cJ)\) is admissible if and only if \(o(\cJ)\leq 2|F(J)|\). As \((\eps,\cJ)\) is an edge-extension \(|F(J)|=|F|-1\). Therefore \((\eps,\cJ)\) is admissible if and only if \(o(\cJ)\leq 2|F|-2\).

If \(c_s=c_t\) then \(O(\cJ)=O(\cH)\) and so \((\eps,\cJ)\) is admissible if and only if \(o(\cH)\leq 2|F|-2\). If \(c_s\neq c_t\) and \(|\{c_s,c_t\}\cap O(\cH)|=1\) then \(O(\cJ)=(O(\cH)\backslash\{c_s\})\cup\{c_t\}\) or \(O(\cJ)=(O(\cH)\backslash\{c_t\})\cup\{c_s\}\). Therefore \(o(\cJ)=o(\cH)\) and so \((\eps,\cJ)\) is admissible if and only if \(o(\cH)\leq 2|F|-2\). If \(c_s\neq c_t\) and \(\{c_s,c_t\}\subset O(\cH)\) then \(O(\cJ)=O(\cH)\backslash\{c_s,c_t\}\). Therefore \(o(\cJ)=o(\cH)-2\) and so \(\cJ\) is admissible if and only if \(\cH\) is admissible. Otherwise \(c_s\neq c_t\) and \(\{c_s,c_t\}\cap O(\cH)=\emptyset\) in which case \(O(\cJ)=O(\cH)\cup\{c_s,c_t\}\), \(o(\cJ)=o(\cH)+2\) and \((\eps,\cJ)\) is admissible if and only if \(o(\cH)\leq 2|F|-4\).

Proper graphs \[sec4500\]

The aim of this section is to extend the correspondence between proper pairs and proper extensions to a correspondence with subgraphs of an associated graph \(\BH\).

\[def4510\] The multigraph \(\bf{B=\BH}\) is the multigraph with vertex set \(V(A)=V\cup C\cup\{v^{\lambda}\}\) and edge-set \(E(A)=\{vc\,|\,v\in V\mbox{ and }c\in M(v)\}\cup\{(v^{\lambda}c,\Lk)\}\cup\{(c_kc_k,\Ek)\,|\,c_k\in C\}\).

\[lem4525\] If \(\cH\) is a proper \(C\)-edge-coloured \(r\)-free-type graph of order \(n\) and \(B=\BH\) then \(d(B,v_i)=n-r\) for all \(v_i\in V(B)\cap V\) and \(d(B,c_k)=(n-r)-\xk\) for all \(c_k\in C\).

Vertex \(v_i\in V(B)\cap V\) is the end of an edge \(v_ic_k\) for every \(c_k\in C\) except for those \(r\) vertices \(c_k\in C\) which correspond to colours used in \(\cH\) on an edge which has \(v_i\) as an end. Therefore \(d(B,v_i)=|C|-r=n-r\) for all \(v_i\in V\).

Vertex \(c_k\in C\) is the end of an edge \(v_ic_k\) for every \(v_i\in V\) except those \(2\ek+\lk\) vertices which, in \(\cH\), are the end of an edge of colour \(c_k\). Furthemore \(c_k\) is the end of \(\Ek\) loops and \(\Lk\) edges \(v^{\lambda}c_k\) so \(d(B,c_k)=r-(2\ek+\lk)+2\Ek+\Lk=(n-r)-\xk\).

\[def4520\] If \(c_k\in C\) then the graph corresponding to a -suitable pair \((S,\theta)\) is the graph \(A=A(S,\theta)\) with vertex-set \(V(A)=V\cup C\) and edge-set \(E(A)=\{vc\,|\,\theta(v)=c\mbox{ for some }v\in C\mbox{ and }c\in S\}\).

\[lem4530\] If \(c_k\in C\) then the graph \(A=A(S,\theta)\) corresponding to a \(c_k\)-suitable pair \((S,\theta)\) is a uniquely defined subgraph of \(\BH\).

\(A\) is uniquely defined because, trivially, \(V(A)=V\cup C\) is uniquely defined and, because \(\theta\) is well-defined, \(E(A)\) is uniquely defined. If \(B=\BH\) then \(V(A)=V(B)\backslash\{v^{\lambda}\}\) and, because \(\theta(v)\in M(v)\) for all \(v\in V\) it follows that \(E(A)\subset E(B)\). Therefore \(A\) is a subgraph of \(B\).

\[def4540\] A graph \(A\) is a -suitable graph if and only if there exists some \(c_k\)-suitable pair \((S,\theta)\) for which \(A\) is the graph corresponding to \((S,\theta)\).

\[lem4550\] A graph \(A\triangleleft\BH\) is \(c_k\)-suitable if and only if \(V(A)=V\cup C\) and (\[lem45501\])-(\[lem45503\]) hold.

1. \(\Delta(A)=1\) \[lem45501\]

2. \(d(A,v)=1\) for all \(v\in V\) \[lem45502\]

3. \(d(A,c_k)=0\) \[lem45503\]

Suppose \((S,\theta)\) is a \(c_k\)-suitable pair. Let \(A=A(S,\theta)\) be the graphh corresponding to \((S,\theta)\). By definition \(V(A)=V\cup C\) and \(E(A)=\{vc\,|\,\theta(v)=c\mbox{ for some }v\in V\mbox{ and }c\in S\}\). Now, because \(\theta\) is well-defined and injective it follows that \(d(A,v)=1\) for all \(v\in V\) and \(\Delta(A)=1\). As \((S,\theta)\) is \(c_k\)-suitable it follows that \(c_k\notin S\) and therefore \(vc_k\notin E(A)\) for all \(v\in V\). Hence \(d(A,c_k)=0\).

If \(A\) satisfies (\[lem45501\])-(\[lem45503\]) let \(S=\{c_j\in C\,|\, d(A,c_j)=1\}\) and let \(\theta:V\rightarrow S\) be defined by \(\theta(v_i)=c_j\) if and only if \(v_ic_j\in E(A)\). Then, by definition, \(S\subset C\) and, from (\[lem45501\]) and (\[lem45502\]), \(\theta\) is bijective. Hence \(|S|=|V|=r\). Finally, from (\[lem45503\]), it follows that \(c_k\notin S\). Therefore \((S,\theta)\) is \(c_k\)-suitable.

The proof of Lemma \[lem4550\] suggests the following definition for the \(c_k\)-suitable pair corresponding to a \(c_k\)-suitable graph.

\[def4560\] If \(c_k\in C\) then the -suitable pair corresponding to a -suitable graph \(A\) is the pair \((S,\theta)\) where \(S=\{c_j\in C\,|\, d(A,c_j)=1\}\) and \(\theta:V\rightarrow S\) is defined by \(\theta(v_i)=c_j\) if and only if \(v_ic_j\in E(A)\).

\[lem4570\] If \(c_k\in C\) then the \(c_k\)-suitable pair corresponding to a \(c_k\)-suitable graph is a uniquely defined \(c_k\)-suitable pair.

Let \(A\) be a \(c_k\)-suitable graph and let \((S,\theta)\) be the corresponding \(c_k\)-suitable pair. Trivially, \(S\) is uniquely defined. By (\[lem45502\]) of Lemma \[lem4550\] it follows that \(\theta\) is well-defined. Therefore \((S,\theta)\) is uniquely defined. The proof that \((S,\theta)\) is \(c_k\)-suitable is the same as the end of the proof of Lemma \[lem4550\].

The reason for introducing the vertex \(v^{\lambda}\) in \(\BH\) is for edges \(v^{\lambda}c_k\) to play a similar role for loop extensions as loops in \(\BH\) play for edge-extensions.

\[def4580\] If \(\lambda\in\Lambda\) then the graph corresponding to a -proper pair \((S,\theta)\) is the graph \(A\) with vertex-set \(V(A)=V(A')\cup\{v^{\lambda}\}\) and edge-set \(E(A)=E(A')\cup\{v^{\lambda}\phi(\lambda)\}\) where \(A'\) is the graph corresponding to \(\phi(\lambda)\)-suitable pair \((S,\theta)\).

\[lem4590\] If \(\lambda\in\Lambda\) then the graph corresponding to a \(\phi(\lambda)\)-proper pair is a uniquely defined subgraph of \(\BH\).

The uniqueness of the graph \(A\) corresponding to the \(\phi(\lambda)\)-proper pair \((S,\theta)\) follows from the uniqueness of the graph \(A'\) corresponding to the \(\phi(\lambda)\)-suitable pair \((S,\theta)\) and the definition of \(V(A)=V(A')\cup\{v^{\lambda}\}\) and \(E(A)=E(A')\cup\{v^{\lambda}\phi(\lambda)\}\). \(A'\) is a subgraph of \(\BH\) because \(V(A')=V(A)\cup\{v^{\lambda}\}=V\cup C\cup\{v^{\lambda}\}=V(B)\) and \(E(A')=E(A)\cup\{v^{\lambda}\phi(\lambda)\}\), \(E(A)\subseteq E(B)\) and \(v^{\lambda}\phi(\lambda)\in E(B)\).

\[def4600\] If \(\lambda\in\Lambda\) then a graph \(A\) is a -proper graph if and only if there is some \(\phi(\lambda)\)-proper pair \((S,\theta)\) for which \(A\) is the corresponding graph.

\[lem4610\] A graph \(A\triangleleft\BH\) is \(\phi(\lambda)\)-proper if and only if \(V(A)=V\cup C\cup\{v^{\lambda}\}\) and (\[lem46101\])-(\[lem46103\]) hold.

1. \[lem46101\] \(\Delta(A)=1\)

2. \[lem46102\] \(d(A,v)=1\) for all \(v\in V\)

3. \[lem46103\] \((v^{\lambda}\phi(\lambda),1)\in E(A)\)

Suppose \((S,\theta)\) is \(\phi(\lambda)\)-proper. By Lemma \[lem4180\] \((S,\theta)\) is \(\phi(\lambda)\)-suitable. Let \(A'\) be the graph corresponding to the \(\phi(\lambda)\)-suitable pair \((S,\theta)\). Then, by definition, \(A=(V(A),E(A))\) where \(V(A)=V(A')\cup\{v^{\lambda}\}\) and \(E(A)=E(A')\cup\{v^{\lambda}\phi(\lambda)\}\). Therefore \(d(A,u)=d(A',u)\) for all \(u\in V(A')\backslash\{v^{\lambda},\phi(\lambda)\}\) and \(d(A',\phi(\lambda))=d(A,\phi(\lambda))+1\). By Lemma \[lem4550\] (\[lem45503\]) it follows that \(d(A,\phi(\lambda))=1\). Therefore, as \(d(A',v^{\lambda})=1\) (\[lem46101\]) and (\[lem46102\]) hold. Finally (\[lem46103\]) holds by definition.

Now suppose that \(A\) is a graph with vertex-set \(V(A)=V\cup C\) which satisfies (\[lem46101\])-(\[lem46103\]) and let \(A'\) to be the graph with vertex-set \(V(A')=V(A)\backslash\{v^{\lambda}\}\) and edge-set \(E(A')=E(A)\backslash\{v^{\lambda}\phi(\lambda)\}\). Then, if \(A'\) is \(\phi(\lambda)\)-suitable, it follows that \(A\) is \(\phi(\lambda)\)-proper.

By construction \(d(A',u)=d(A,u)\) for all \(u\in V(A)\backslash\{\phi(\lambda)\}\) and \(d(A',\phi(\lambda))=d(A,\phi(\lambda))-1\). If follows from (\[lem46101\]) and (\[lem46102\]) that \(\Delta(A')=1\) and \(d(A',v)=1\) for all \(v\in V\) and from (\[lem46101\]) and (\[lem46103\]) that \(d(A',\phi(\lambda))\). Now, by Lemma \[lem4550\] \(A'\) is \(\phi(\lambda)\)-suitable and hence \(A\) is \(\phi(\lambda)\)-proper.

\[def4615\] The -proper pair corresponding to a -proper graph \(A\) is the \(\phi(\lambda)\)-suitable pair corresponding to \(A'=(V(A'),E(A'))\) where \(V(A')=V(A)\backslash\{v^{\lambda}\}\) and \(E(A')=E(A)\backslash\{v^{\lambda}\phi(\lambda)\}\).

\[lem4625\] The \(\phi(\lambda)\)-proper pair corresponding to a \(\phi(\lambda)\)-proper graph is a uniquely defined \(\phi(\lambda)\)-proper pair.

Let \((S,\theta)\) be the \(\phi(\lambda)\)-proper pair corresponding to a \(\phi(\lambda)\)-proper graph \(A\). By Lemma \[lem4590\] \((S,\theta)\) is a uniquely defined \(\phi(\lambda)\)-suitable pair. Therefore, by Lemma \[lem4180\] \((S,\theta)\) is a uniquely defined \(\phi(\lambda)\)-proper pair.

\[def4630\] If \(\eps\in F\) and \(\{c_s,c_t\}\subseteq C\) then the graph corresponding to a -proper pair \(\{(S,\theta_S,c_s),(T,\theta_T,c_t)\}\) is the graph \(A_S\cup A_T\cup\lambda\) where \(A_S\) is the graph corresponding to the \(\phi(\eps)\)-suitable pair \((S,\theta_S)\), \(A_T\) is the graph corresponding to the \(\phi(\eps)\)-suitable pair \((T,\theta_T)\) and \(\lambda=(\{\phi(\eps)\},(\phi(\eps)\phi(\eps)))\).

\[lem4640\] If \(\eps\in F\) and \(\{c_s,c_t\}\subseteq C\) then the graph corresponding to a \((\phi(\eps),c_s,c_t)\)-proper pair \(\{(S,\theta_S,c_s),(T,\theta_T,c_t)\}\) is a uniquely defined subgraph of \(\BH\).

This follows because, by definition, the corresponding graph is \(A=A_S\cup A_T\cup \lambda\), where \(A_S\) is, by Lemma \[lem4530\], the uniquely defined subgraph of \(\BH\) corresponding to \((S,\theta_S)\) and \(A_T\) is the uniquely defined subgraph of \(\BH\) corresponding to \((T,\theta_T)\) and, by definition, \(\lambda=(\phi(\eps),\phi(\eps)\phi(\eps))\) is uniquely defined.

\[def4650\] A graph \(A\) is a -proper graph if and only if \(A\) is the graph corresponding to some \((\phi(\eps),c_s,c_t)\)-proper pair.

\[lem4660\] If \(\eps\in F\) and \(\{c_s,c_t\}\subseteq C\) then a graph \(A\triangleleft\BH\) is \((\phi(\eps),c_s,c_t)\)-proper if and only if \(V(A)=V\cup C\) and (\[lem46601\])-(\[lem46605\]) hold.

1. \[lem46601\] \(\Delta(A)=2\)

2. \[lem46602\] \(d(A,v)=2\) for all \(v\in V\)

3. \[lem46603\] \(\phi(\eps)\phi(\eps)\in E(A)\)

4. \[lem46604\] \(|E(A)|=2r+1\)

5. \[lem46605\] If \(c_k\in\{c_s,c_t\}\) then \(d(A,c_k)\leq 1\) and if \(c_k=c_s=c_t\) then \(d(A,c_k)=0\).

Suppose \(A\) is a \((\phi(\eps),c_s,c_t)\)-proper graph. Then, by definition, there is some \((\phi(\eps),c_s,c_t)\)-proper pair \(\{(S,\theta_S,c_s),(T,\theta_T,c_t)\}\) for which \(A\) is the graph corresponding to \(\{(S,\theta_S,c_s),(T,\theta_T,c_t)\}\). It follows, by definition, that \(A=A_S\cup A_T\cup\{\lambda\}\) where \(A_S\) is the \(\phi(\eps)\)-suitable graph corresponding to the \(\phi(\eps)\)-suitable pair \((S,\theta_S)\), \(A_T\) is the \(\phi(\eps)\)-suitable graph corresponding to the \(\phi(\eps)\)-suitable pair \((T,\theta_T)\) and \(\lambda=(\{\phi(\eps)\},\phi(\eps)\phi(\eps))\).

Obviously, \(\phi(\eps)\phi(\eps)\in E(A)\), so (\[lem46603\]) holds.

As \(\{(S,\theta_S,c_s),(T,\theta_T,c_t)\}\) is \((\phi(\eps),c_s,c_t)\)-proper it follows, by definition, that \(c_s\notin S\) and \(c_t\notin T\). Therefore, if \(c_k\in\{c_s,c_t\}\), it follows that \(d(A,c_k)\leq 1\) and, if \(c_k=c_s=c_t\), then \(d(A,c_k)=0\).

Because \(A_S\) and \(A_T\) are both \(\phi(\eps)\)-suitable it follows from Lemma \[lem4550\] that \(\Delta(A_S\cup A_T)=2\), \(d(A_S\cup A_T,v)=1\) for all \(v\in V\) and \(d(A_S\cup A_T,\phi(\eps))=0\). Now, because \(d(A,u)=d(A_S\cup A_T,u)\) for all \(u\in V(A)\backslash\{\phi(\eps)\}\) and \(d(A,\phi(\eps))=d(A_S\cup A_T,\phi(\eps))+2\) it follows that \(\Delta(A)=2\) and \(d(A,v)=2\) for all \(v\in V\).

Finally, because \(\phi(\eps)\phi(\eps)\in E(A)\) it follows that \(|E(A)|=|E(A_S)|+|E(A_T)|+1\) and therefore, as \(A_S\) and \(A_T\) are both \(\phi(\eps)\)-suitable \(|E(A)|=2r+1\).

Now suppose that \(A\triangleleft\BH\) satisfies (\[lem46601\])-(\[lem46605\]). Let \(A'\) be the graph with vertex-set \(V(A')=V(A)\) and edge-set \(E(A')=E(A)\backslash\{\phi(\eps)\phi(\eps)\}\). From (\[lem46601\]) and (\[lem46602\]) it follows that \(A'=A_1'\cup A_2'\cup\ldots\cup A_k'\) for some \(k\in\bf{N}\) where, for all \(i\in [k]\), \(A_i'\) is either a path component of even length or a cycle component of even length.

If \(A_i'=(v_0e_1v_1e_2,\ldots,v_{2m-1}e_{2m})\) then let \(E_{i,1}'=\{e_1,e_3,\ldots,e_{2m-1}\}\), \(E_{i,2}=\{e_2,e_4,\ldots,e_{2m}\}\), \(V_{i,1}'=\{v_0,v_1,\ldots,v_{2m-1}\}\), \(V_{i,2}'=\{v_1,v_2,\ldots,v_{2m}\}\), \(A_{i,1}'=(V_{i,1}',E_{i,1}')\) and \(A_{i,2}'=(V_{i,2}',E_{i,2}')\). Then let \(A_S'=\cup_{i\in [k]}A_{i,1}'\) and \(A_T'=\cup_{i\in [k]}A_{i,2}'\).

Now, if \(d(A_S',c_s)=0\) and \(d(A_T',c_t)=0\) then let \(A_S=A_S'\) and \(A_T=A_T'\). Otherwise \(d(A_S,c_t)=0\) and \(d(A_T,c_s)=0\). In this case let \(A_S=A_T'\) and \(A_T=A_S'\).

\(A_S\) is \(c_s\)-suitable and \(A_T\) is \(c_t\)-suitable. Let \((S,\theta_S)\) be the \(\phi(\eps)\)-suitable pair corresponding to \(A_S\) and let \((T,\theta_T)\) be the \(\phi(\eps)\)-suitable pair corresponding to \(A_T\). Then \(A\) is the graph corresponding to the \((\phi(\eps),c_s,c_t)\)-proper pair \(\{(S,\theta_S,c_s),(T,\theta_T,c_t)\}\).

A \((\phi(\eps),c_s,c_t)\)-proper subgraph \(A\) does not uniquely define a proper pair. The decomposition of \(A\) into suitable subgraphs is not, in general, unique. In the next section it is shown that a certain type of decomposition of \(A\) uniquely defines a proper pair.

Suitable decompositons of proper graphs \[sec4670\] In this section the aim is to show that a proper extension corresponds uniquely to a suitable decomposition of a proper graph.

\[def4675\] A \(\{c_s,c_t\}\)-suitable decomposition of a -proper graph \(A\) is a decomposition \(\cA=\{A_S,A_T,\lambda\}\) where \(A_S\) and \(A_T\) are both \(\phi(\eps)\)-suitable graphs, \(d(A_S,c_s)=0\), \(d(A_T,c_t)=0\) and \(\lambda=(\phi(\eps),\phi(\eps)\phi(\eps))\).

\[def4680\] A suitably decomposed -proper graph is a pair \((A,\cA)\) where \(A\) is a \((\phi(\eps),c_s,c_t)\)-proper graph and \(\cA\) is a \(\{c_s,c_t\}\)-suitable decomposition of \(A\).

\[def4683\] The -proper pair corresponding to a suitably decomposed -proper graph \((A,\cA)\) is the pair \(\{(S,\theta_S,c_s),(T,\theta_T,c_t)\}\) where \((S,\theta_S)\) is the \(\phi(\eps)\)-suitable pair corresponding to \(A_S\), \((T,\theta_T)\) is the \(\phi(\eps)\)-proper pair correpsonding to \(A_T\) and \(\cA=(A_S,A_T,\lambda)\) .

\[lem4684\] If \(\eps\in F\) then the \((\phi(\eps),c_s,c_t)\)-proper pair corresponding to a suitably decomposed \((\phi(\eps),c_s,c_t)\)-proper graph is a uniquely defined \((\phi(\eps),c_s,c_t)\)-proper pair.

\(\{(S,\theta_S,c_s),(T,\theta_T,c_t)\}\) is uniquely defined because, by definition, \((S,\theta_S)\) is the \(\phi(\eps)\)-suitable pair corresponding to the \(\phi(\eps)\)-suitable graph \(A_S\) and \((T,\theta_T)\) is the \(\phi(\eps)\)-suitable pair corresponding to the \(\phi(\eps)\)-suitable graph \(A_T\). Therefore, by Lemma \[lem4625\], \((S,\theta_S)\) and \((T,\theta_T)\) are both uniquely defined \(\phi(\eps)\)-suitable pairs and hence \(\{(S,\theta_S,c_s),(T,\theta_T,c_t)\}\) is uniquely defined.

By definition \((S,\theta_S)\) and \((T,\theta_T)\) are \(\phi(\eps)\)-suitable and \(\{c_s,c_t\}\subset C\backslash\{\phi(\eps)\}\). As \(d(A_S,c_s)=0=d(A_T,c_t)=0\) it follows, by Lemma \[lem4357\] that \(c_s\notin S\) and \(c_t\notin T\). As \((S,\theta_S)\) and \((T,\theta_T)\) are both \(\phi(\eps)\)-suitable it follows that \(\phi(\eps)\notin S\) and \(\phi(\eps)\notin T\). Finally, \(\theta_S(u)\neq\theta_T(u)\) for all \(u\in V\) because \(E(A_S)\cap E(A_T)=\emptyset\). Therefore \(\{(S,\theta_S,c_S),(T,\theta_T,c_t)\}\) is a \((\phi(\eps),c_s,c_t)\)-proper pair.

Lemma \[lem46845\] is very useful in Section \[sec4700\]

\[lem46845\] If \(\eps\in F\) and \(\{(S,\theta_S,c_s),(T,\theta_T,c_t)\}\) and \((A,\cA)\) are corresponding \((\phi(\eps),c_s,c_t)\)-pair and suitably decomposed \((\phi(\eps),c_s,c_t)\)-proper graph then \(d(A,c_k)=2\) if and only if \(c_k\in S\cap T\), \(d(A,c_k)\geq 1\) if and only if \(c_k\in S\cup T\) and \(d(A,c_k)=0\) if and only if \(c_k\in C\backslash (S\cup T)\) for all \(c_k\in C\backslash\{\phi(\eps)\}\).

By definition \(A=A_S\cup A_T\cup\lambda\) where \(A_S\) is the \(\phi(\eps)\)-suitable graph corresponding to \((S,\theta_S)\), \(A_T\) is the \(\phi(\eps)\)-suitable graph corresponding to \((T,\theta_T)\) and \(\lambda=(\phi(\eps),\phi(\eps)\phi(\eps))\). By Lemma \[lemXXXX\] \(d(A_S,c_k)=1\) if and only if \(c_k\in S\), \(d(A_T,c_k)=1\) if and only if \(c_k\in T\). Therefore \(d(A,c_k)=d(A_S,c_k)+d(A_T,c_k)\) for all \(c_k\in C\backslash\{\phi(\eps)\}\). It follows that \(d(A,c_k)=2\) if and only if \(c_k\in S\cap T\), \(d(A,c_k)\geq 1\) if and only if \(c_k\in S\cup T\) and \(d(A,c_k)=0\) if and only if \(c_k\in C\backslash (S\cup T)\) for all \(c_k\in C\backslash\{\phi(\eps)\}\).

\[def4685\] If \(vw=\eps\in F\) then the proper -extension corresponding to a suitably decomposed -proper graph \((A,\cA)\) is the proper \(\eps\)-extension corresponding to the \((\phi(\eps),c_s,c_t)\)-proper pair corresponding to \((A,\cA)\).

\[lem4690\] If \(\eps\in F\) then the proper \(\eps\)-extension corresponding to a suitably decomposed \((\phi(\eps),c_s,c_t)\)-proper graph is a uniquely defined proper \(\eps\)-extension of \(\cH\).

Let \(\cJ\) be the proper \(\eps\)-extension corresponding to the suitably decomposed \((\phi(\eps),c_s,c_t)\)-proper graph \((A,\cA)\). Then, by Lemma \[lem4206\], it follows that \(\cJ\) is a uniquely defined proper \(\eps\)-extension of \(\cH\) if and only if \(\{(S,\theta_S,c_S),(T,\theta_T,c_t)\}\), where \((S,\theta_S)\) is the \(\phi(\eps)\)-suitable pair corresponding to \(A_S\) and \((T,\theta_T)\) is the \(\phi(\eps)\)-suitable pair corresponding to \(A_T\), is a uniquely defined \((\phi(\eps),c_s,c_t)\)-proper pair. This follows from Lemma \[lem4684\]

Ryser proper graphs \[sec4700\] In this section the aim is to give necessary and sufficient conditions for the extension corresponding to a proper graph to be Ryser.

\[def4710\] If \(\lambda\in\Lambda\) then a \(\phi(\lambda)\)-proper graph \(A\) is a Ryser -proper graph if and only if the \(\phi(\lambda)\)-proper pair corresponding to \(A\) is Ryser.

\[lem4720\] If \(\lambda\in\Lambda\) then a \(\phi(\lambda)\)-proper graph \(A\) is Ryser if and only if \(d(A,c_k)=1\) for all critical \(c_k\in C\backslash\{\phi(\lambda)\}\).

By definition \(A\) is Ryser if and only if the \(\phi(\lambda)\)-proper pair \((S,\theta)\) corresponding to \(A\) is Ryser. From Lemma \[lem4350\] \((S,\theta)\) is Ryser if and only if \(S\) contains every critical \(c_k\in C\backslash\{\phi(\eps)\}\). The result follows from Lemma \[lem4357\] which says that \(c_k\in S\) if and only if \(d(A,c_k)=1\).

\[def4730\] A \((\phi(\eps),c_s,c_t)\)-proper graph \(A\) is a Ryser -proper graph if and only if the \(\phi(\eps)\)-proper pair corresponding to \(A\) is Ryser.

\[lem4740\] If \(\eps\in F\) then a \((\phi(\eps),c_s,c_t)\)-proper graph \(A\) is Ryser if and only if (\[lem47402\])-(\[lem47404\]) hold.

1. \[lem47402\] If \(c_k\in C\backslash\{\phi(\eps),c_s,c_t\}\) is critical then \(d(A,c_k)=2\) and if \(c_k\in C\backslash\{\phi(\eps),c_s,c_t\}\) is semi-critical then \(d(A,c_k)\geq 1\).

2. \[lem47403\] If \(c_s\neq c_t\) and \(c_k\in\{c_s,c_t\}\) then \(\xk>0\) and if \(\xk=\{1,2\}\) then \(d(A,c_k)\geq 1\).

3. \[lem47404\] If \(c_s=c_t\) and \(c_k\in\{c_s,c_t\}\) then \(\xk\geq 2\)

If \(A\) is Ryser then, by definition, the corresponding \(\phi(\eps)\)-proper pair \(\{(S,\theta_s,c_s),(T,\theta_t,c_t)\}\) is Ryser.

If \(c_k\in C\backslash\{\phi(\eps),c_s,c_t\}\) is critical then by Lemma \[lem4350\] (\[lem43501\]) it follows that \(c_k\in S\cap T\) and so by Lemma \[lem46845\] it follows that \(d(A,c_k)=2\). If \(c_k\in C\backslash\{\phi(\eps),c_s,c_t\}\) is semi-critical then, again by Lemma \[lem4350\] (\[lem43501\]), it follows that \(c_k\in S\cup T\) and so, by Lemma \[lem46845\], \(d(A,c_k)\geq 1\). If \(c_s\neq c_t\) and \(c_k\in\{c_s,c_t\}\) then, by Lemma \[lem4350\] (\[lem43502\]), it follows that \(\xk> 0\) and if \(\xk\in\{1,2\}\) then \(c_k\in S\cup T\), in which case it follows from Lemma \[lem4680\] that \(d(A,c_k)\geq 1\). Finally, if \(c_s=c_t\) and \(c_k\in\{c_s,c_t\}\) then, by Lemma \[lem4350\], \(\xk\geq 2\).

Now suppose that \(A\) is \((\phi(\eps),c_s,c_t)\)-proper and satisfies (\[lem47402\])-(\[lem47404\]). Let \(\{(S,\theta_s,c_s),(T,\theta_t,c_t)\}\) be the \(\phi(\eps)\)-proper pair corresponding to \(A\). Lemma \[lem46845\] implies that if \(c_k\in C\backslash\{\phi(\eps),c_s,c_t\}\) is critical then, as \(d(A,c_k)=2\), \(c_k\in S\cap T\) and if \(c_k\in C\backslash\{\phi(\eps),c_s,c_t\}\) is semi-critical then, as \(d(A,c_k)\geq 1\), \(c_k\in S\cup T\). If \(c_s\neq c_t\) and \(c_k\in\{c_s,c_t\}\) then, from (\[lem47403\]), \(\xk>0\) and if \(\xk\in\{1,2\}\) then, as \(d(A,c_k)\geq 1\), from Lemma \[lem46845\] it follows that \(c_k\in S\cup T\). Finally, if \(c_s=c_t\) and \(c_k\in\{c_s,c_t\}\) then, by (\[lem47404\]) \(\xk\geq 2\). Therefore, by Lemma \[lem4350\], \(\{(S,\theta_s,c_s),(T,\theta_t,c_t)\}\) is Ryser. Hence \(A\) is Ryser.

Admissible subgraphs \[sec4750\]

In this section the aim is to characterise the proper graphs whose corresponding extension is admissible.

As shown in Lemma \[lem4380\] the condition for a proper loop extension to be admissible is vacuous. Consequently it is of no surprise to learn that admissible subgraphs, in the case of a loop-extension, are precisely the proper subgraphs.

\[def4760\] If \(\lambda\in\Lambda\) then a \(\phi(\lambda)\)-proper graph \(A\) is an admissible -proper graph if and only if there the \(\phi(\lambda)\)-proper pair corresponding to \(A\) is admissible.

\[lem4780\] If \(\lambda\in\Lambda\) and \(A\) is a \(\phi(\lambda)\)-proper graph then \(A\) is admissible.

If \(A\) is \(\phi(\lambda)\)-proper then, by definition, the \(\phi(\lambda)\)-proper pair corresponding to \(A\) is \(\phi(\lambda)\)-proper. By Corollary \[cor4400\] \((S,\theta)\) is admissible. Therefore \(A\) is admissible by definition.

In the case of an edge-extension the condition for admissibilty is non-trivial.

\[def4790\] If \(\eps\in F\) and \(A\) is a \((\phi(\eps),c_s,c_t)\)-proper graph then \(A\) is an admissible -proper graph if and only if the \(\phi(\eps)\)-proper pair corresponding to \(A\) is admissible.

\[lem4800\] If \(\eps\in F\) and \(A\) is a \((\phi(\eps),c_s,c_t)\)-proper graph than \(A\) is admissible if and only if \(\{c_s,c_t\}\) are an admissible pair of colours.

\(A\) is admissible, by definition, if and only if the \(\eps\)-proper pair \(\{(S,\theta_s,c_s),(T,\theta_t,c_t)\}\) corresponding to \(A\) is admissible. By Lemma \[lem4430\] \(\{(S,\theta_s,c_s),(T,\theta_t,c_t)\}\) is admissible if and only if \(\{c_s,c_t\}\) are an admissible pair of colours. Therefore \(A\) is admissible if and only if \(\{c_s,c_t\}\) is an admissible pair of colours.

Loop assignments \[sec4820\] In this section the aim is to prove the necessity of the existence of Ryser admissible complete loop assignments for embedding a proper \(C\)-edge-coloured \(r\)-free-type graph of order \(n\) in a proper \(C\)-edge-coloured complete graph of order \(n\).

\[def4830\] A loop assignment for is a map \(y:C\rightarrow [2|F|]^{\star}\) which satisfies \(y(C)\leq 2|F|\).

\[def4840\] A loop assignment for \(\cH\) is complete if and only if \(y(C)=2|F|\).

\[def4850\] A loop assignment for \(\cH\) is Ryser if and only if \(y(c_k)\leq\xk\) holds for all \(c_k\in C\).

\[def4860\] A loop assignment for \(\cH\) is admissible if and only if \(y(c_k)\equiv\xk\bmod{2}\) holds for all \(c_k\in C\).

\[def4870\] A proper \(C\)-edge-coloured \(r\)-free-type graph \(\cH\) of order \(n\) is -embeddable if and only if \(\cH\) can be embedded in a proper \(C\)-edge-coloured complete graph of order \(n\) which has exactly \(\lk+\Lk+y(c_k)\) loops of colour \(c_k\) for all \(c_k\in C\).

\[lem4880\] If \(\cH\) is a proper \(C\)-edge-coloured \(r\)-free-type graph \(\cH\) of order \(n\), \(y\) is a loop-assignment for \(\cH\) and \(\cH\) is \(y\)-embeddable then \(y\) is complete, Ryser and admissible.

If \(\cH\) is \(y\)-embeddable then, by definition, \(\cH\) can be embedded in a proper \(C\)-edge-coloured complete graph \(\cK=(K,(C,\psi))\) of order \(n\) which has exactly \(\lk+\Lk+y(c_k)\) loops of colour \(c_k\) for all \(c_k\in C\).

As \(\cK\) has exactly \(n\) loops it follows that \(l(C)+\lambda(C)+y(C)=n\). Now, because \(l(C)+\lambda(C)=n-2|F|\) it follows that \(y(C)=2|F|\). Therefore \(y\) is complete, by definition.

As \(|C|=n\) and \(d(K,v)=n\) for all \(v\in V(K)\) it follows that \(C(v)=C\) for all \(v\in V(K)\). There are \(r-(2\ek+\lk)\) vertices \(v\in V(K)\cap V(H^{\star})\) which are the end of an edge of colour \(c_k\) of the form \(vw\), where \(w\in V(F\cup\Lambda)\). Every such edge has an end \(w\in V(F\cup\Lambda)\) which is the end of no other edge of colour \(c_k\). There are \((n-r)-(2\Ek+\Lk+y(c_k))\) such vertices and so \(r-(2\ek+\lk)\leq (n-r)-(2\Ek+\Lk+y(c_k))\). It follows from the definition of \(\xk\) that \(\yk\leq\xk\).

Finally, from the definition of \(\xk\) it follows that \(\xk\equiv n+\lk+\Lk\bmod{2}\). Therefore \(\lk+\Lk+\yk\equiv n\bmod{2}\) and, consequently, \(\xk\equiv\yk\bmod{2}\).

\[lem4890\] If a proper \(C\)-edge-coloured \(r\)-free-type graph \(\cH\) of order \(n\) can be embedded in a proper \(C\)-edge-coloured complete graph of order \(n\) then there exists a complete Ryser admissible loop assignment \(y\) such that \(\cH\) is \(y\)-embeddable.

Suppose \(\cH\) is embedded in a proper \(C\)-edge-coloured complete graph \(\cK\) of order \(n\) and let \(y:C\rightarrow\bf{Z}\) be defined by \(\yk=\{v\in V(K)\cap V(F)\,|\,v\mbox{ is the end of a loop of colour }c_k\mbox{ in }\cK\}\). Then, as \(|V(F)|=2|F|\), \(y\) is a loop-assignment for \(\cH\) and \(\cH\) is \(y\)-completable. Therefore, by Lemma \[lem4880\], \(y\) is complete, Ryser and admissible.

For each loop assignment \(y\) a corresponding multigraph \(Q(\cH,y)\) is defined. This multigraph is based on \(\BH\) but has an extra vertex \(v^{\eps}\) and a set of edges, all with \(v^{\eps}\) as an end, which together correspond to the loop-assignment \(y\).

\[def4900\] If \(B=\BH\) then \(Q=Q(y)=Q(\cH,y)\) is the multigraph with vertex-set \(V(Q)=V(B)\cup\{v^{\eps}\}\) and \(E(Q)=E(B)\cup\{(v^{\eps}c_k,\yk)\,|\,c_k\in C\}\).

In other words, \(Q\) is obtained from \(\BH\) by adjoining a new vertex \(v^{\eps}\) and joining \(v^{\eps}\) to \(c_k\) by \(\yk\) edges.

\[def4910\] The multigraph \(Q(\cH,y)\) is complete if and only if \(y\) is complete, admissible if and only if \(y\) is admissible and Ryser if and only if \(y\) is Ryser.

\[lem4920\] The multigraph \(Q(\cH,y)\) is complete if and only if \(d(Q,v^{\eps})=2|F|\), admissible if and only if \(d(Q,c_k)\equiv (n-r)\bmod{2}\) for all \(c_k\in C\) and Ryser if and only if \(d(Q,c_k)\leq n-r\) for all \(c_k\in C\).

From the definition of \(Q=Q(\cH,y)\) it follows that \(d(Q,v^{\eps})=y(C)\). Therefore \(Q\) is complete if and only if \(d(Q,v^{\eps})=2|F|\). Also from the definition of \(Q\) it follows that \(d(Q,c_k)=d(B,c_k)+\yk\). Therefore, because \(d(B,c_k)=(n-r)-\xk\) it follows that \(Q\) is Ryser if and only if \(d(Q,c_k)\leq n-r\) for all \(c_k\in C\) and admissible if and only if \(d(Q,c_k)\equiv (n-r)\bmod{2}\) for all \(c_k\in C\).

\[lem4925\] If \(\cH\) is a proper \(C\)-edge-coloured \(r\)-free-type multigraph of order \(n\) with no free-loops and \(y\) is a Ryser admissible complete loop assignment for \(\cH\) then \(Q(\cH,y)\) is a \((r+1,n)\)-\(B\)-type multigraph.

By definition, if \(Q=Q(\cH,y)\), then \(V(Q)=V\cup\{v^{\lambda}\}\cup C\). \(|V\cup\{v^{\lambda}\}|=r+1\), \(|C|=n\), \(Q\) has \((n-(r+1)+1)/2=(n-r)/2\) loops all of which have their ends in \(C\) and every non-loop edge of \(Q\) has an end in \(V\cup\{v^{\lambda}\}\) and an end in \(C\). Moreover, by Lemma \[lemXXXX\], \(d(Q,v_i)=n-r\) for all \(v_i\in V\cup\{v^{\eps}\}\) and \(d(Q,c_k)=n-r-\xk+\yk\equiv (n-r)\bmod{2}\) because \(y\) is admissible. Therefore \(Q\) is an \((r+1,n)\)-\(B\)-type multigraph.

In Lemma \[lem4930\] the slightly surprising fact that a Ryser admissible proper \(C\)-edge-coloured \(r\)-free-type graph always has a Ryser admissible complete loop assignment is proved.

\[lem4930\] If \(\cH\) is a Ryser admissible proper \(C\)-edge-coloured \(r\)-free-type graph then there is a Ryser admissible complete loop assignment for \(\cH\)

If \(n-r\leq 1\) then \(F=\emptyset\). Therefore \(y:C\rightarrow\bf{Z}\) defined by \(\yk=0\) for all \(c_k\in C\) is a complete loop assignment. Moreover, \(y\) is Ryser because \(\cH\) is Ryser and therefore \(\xk\geq 0\) for all \(c_k\in C\). If \(n\) is odd then, because \(\cH\) is admissible \(\lk+\Lk\leq 1\) for all \(c_k\in C\) and therefore, because \(l(C)+\lambda(C)=n\), it follows that \(\lk+\Lk=1\) for all \(c_k\in C\). If \(n\) is even then, because \(\cH\) is admissible, \(o(\cH)\leq 2|F|\) and because \(|\Lambda|=n-r\) it follows that \(\lk+\Lk\) is even for all \(c_k\in C\). Therefore, because \(\xk\equiv n+\Lk+\lk\bmod{2}\) for all \(c_k\in C\), it follows that \(\xk\equiv\yk\bmod{2}\) for all \(c_k\in C\). Therefore \(y\) is loop-admissible.

Suppose that \(n-r\geq 2\) and let \(y':C\rightarrow\bf{Z}\) be defined by \(y'(c_k)=1\) if and only if \(c_k\in O(\cH)\) and \(y'(c_k)=0\) if and only if \(c_k\in C\backslash O(\cH)\). Then, because \(\cH\) is admissible \(y'(C)=o(\cH)\leq 2|F|\) and so \(y'\) is a loop assignment for \(\cH\). The remainder of the proof involves proving that, in general, \(y'\) can be augmented to a complete Ryser admissible loop assignment \(y\).

Let \(Q'=Q(\cH,y')\). From the definition of \(Q\) it follows that \(d(Q',v)=n-r\) for all \(v\in V\) and \(d(Q',v^{\lambda})+d(Q',v^{\eps})=|\Lambda|+o(\cH)\). Now, because the vertices of \(C\) have \(|F|\) incident loops and the graph obtained from \(Q'\) by removing all the loops is bipartite it follows that \(d(Q',C)=r(n-r)+|\Lambda|+O(\cH)+2|F|\).

As \(n-r\geq 2\) and \(2|F|\leq n-r\) it follows that \(2|F|\leq (n-r)(n-r-1)=(n-r)^2-(n-r)\) and so \(4|F|+|\Lambda|\leq (n-r)^2\). Therefore \(d(Q',C)\leq n(n-r)-(2|F|-o(\cH))\). It follows that there is a map \(y'':C\rightarrow\bf{Z}\) with the property that \(y''(c_k)\leq (n-r)-d(Q',c_k)\) and \(y''(c_k)\) is even for all \(c_k\in C\) and \(y''(C)=2|F|-O(\cH)\). Let \(y:C\rightarrow\bf{Z}\) be defined by \(\yk=y'(c_k)+y''(c_k)\) for all \(c_k\in C\).

Consider \(Q=Q(\cH,y)\). Firstly \(d(Q,v^{\eps})=y'(C)+y''(C)=O(\cH)+2|F|-O(\cH)=2|F|\). Therefore, by Lemma \[lem4920\], \(y\) is a complete loop assignment for \(\cH\). Secondly, as \(y''(c_k)\leq (n-r)-d(Q',c_k)\) for all \(c_k\in C\) it follows that \(d(Q,c_k)=d(Q',c_k)+y''(c_k)\leq n-r\). Therefore, by Lemma \[lem4920\], \(y\) is Ryser. Finally, as \(y''(c_k)\) is even for all \(c_k\in C\), then, because \(d(Q',c_k)=d(M,c_k)\) if and only if \(c_k\in C\backslash O(\cH)\) and \(d(Q',c_k)=d(M,c_k)+1\) if and only if \(c_k\in O(\cH)\), it follows that \(d(Q,c_k)\equiv d(Q',c_k)\bmod{2}\equiv (n-r)\bmod{2}\). Therefore, by Lemma \[lem4920\] it follows that \(y\) is admissible.

Compatible extensions \[sec4940\] It may seem that Lemma \[lem4930\] means that the whole issue of loop assignments can be ignored. After all, provided an extension is Ryser admissible it is guarenteed to have a Ryser admissible complete loop assignment. However, it is fairly obvious, and proved in Lemma \[lem4970\], that if \(\cH\) is \(y\)-embeddable then for every \(\mu\in F\cup\Lambda\) there is a Ryser admissible \(\mu\)-extension of \(\cH\) with the “same” Ryser admissible complete loop assignment as \(\cH\). The aim of this section is to give necessary and sufficient conditions for \(\cH\) to have such a compatible extension.

\[def4950\] If \(\lambda\in\Lambda\), \(y\) is a loop assignment for \(\cH\), \(\eps\in F\) and \(\{c_s,c_t\}\subseteq C\) then \(y'=y'(\phi(\eps),c_s,c_t)\) is defined by \[y'(c_k)=\left\lbrace \begin{array}{ccc} \yk & \mbox{if and only if} & c_k\in\{\phi(\eps),c_s,c_t\} \\ \yk-1 & \mbox{if and only if} & c_s\neq c_t, c_k\in\{c_s,c_t\} \\ \yk-2 & \mbox{if and only if} & c_k=c_s=c_t \end{array} \right.\]

\[def4960\] An extension \((\mu,\cJ)\) is -compatible if and only if \(\mu\in \Lambda\) and \(y\) is a Ryser admissible complete loop assignment for \(\cJ\) or \(\mu\in F\) and \(y'=y'(\phi(\eps),c_s,c_t)\) is a Ryser admissible complete loop assignment for \(\cJ\)

\[lem4970\] If \(\cH\) can be embedded in a proper \(C\)-edge-coloured complete graph of order \(n\) then there exists a Ryser admissible complete loop assignment \(y\) for \(\cH\) such that \(\cH\) has a \(y\)-compatible \(\mu\)-extension for every \(\mu\in F\cup\Lambda\).

Suppose that \(\cK\) is a proper \(C\)-edge-coloured complete graph of order \(n\) in which \(\cH\) is embedded. Let \(y:C\rightarrow [2|F|]^{\star}\) be defined by \(\yk=|\{v\in V(K)\cap V(F)\,|\,v\mbox{ is the end of a loop of colour }c_k\mbox{ in }\cK\}|\). As \(|V(F)|=2|F|\) it follows that \(y\) is a loop-assignment for \(\cH\). Moreover, because \(\cK\) has exactly \(\lk+\Lk+\yk\) loops of colour \(c_k\) for all \(c_k\in C\) it follows that \(\cH\) is \(y\)-embeddable.

If \(\mu\in F\cup\Lambda\) and \(\cJ=\cK|_{H\cdot\mu}\) then, as \(\cJ\) is embedded in \(\cK\) and \(\cK\) has exactly \(\lrk+\Lrk+y'(c_k)\) loops of colour \(c_k\) for all \(c_k\in C\), it follows that \(\cJ\) is \(y'\)-embeddable. Therefore, by Lemma \[lem4880\], \(y'\) is a Ryser admissible complete loop assignment for \(\cJ\). Therefore, by definition, \(\cJ\) is a \(y\)-compatible extension of \(\cH\).

In general a Ryser admissible extension is not \(y\)-compatible. In the next two lemmas necessary and sufficient conditions are given for a Ryser admissible proper \(C\)-edge-coloured \(r\)-free-type graph to have a \(y\)-compatible extension. In the case of a loop extension, Lemma \[lem4980\], there is a single conditition, whereas in the case of an edge-extension, Lemma \[lem4990\], there are two conditions.

\[lem4980\] If \(\lambda\in\Lambda\) and \(y\) is a Ryser admissible complete loop assignment for \(\cH\) then a \(\lambda\)-extension is \(y\)-compatible if and only if (\[lem49801\]) holds.

1. If \(\xk-\yk=0\) then \(\edk=1\) for all \(c_k\in C\backslash\{\phi(\lambda)\}\)\[lem49801\]

First it is shown that \(y\) is complete and admissible for a \(\lambda\)-extension \(\cJ\). Then, to prove the lemma, it suffices to show that \(y\) is Ryser for \(\cJ\) if and only if (\[lem49801\]) holds.

Because \(y\) is a complete loop assignment for \(\cH\) it follows, by definition, that \(y(C)=2|F|\). Therefore as \(|F(\cJ)|=|F|\) is follows that \(y\) is a complete loop assignment for \(\cJ\).

It follows from Lemma \[lem4290\] and the definition of \(\xdk\) that \(\xdk=2\edk-2\) if \(c_k\in C\backslash\{\phi(\lambda)\}\) and \(\xdk=2\edk\) if \(c_k=\phi(\lambda)\). Therefore \(x(\cJ,c_k)\equiv\xk\bmod{2}\) holds for all \(c_k\in C\) and, because \(y\) is admissible for \(\cH\), \(y(c_k)\equiv\xk\equiv x(\cK,c_k)\bmod{2}\) for all \(c_k\in C\). So \(y\) is admissible for \(\cJ\)

Now, by definition, \(y\) is Ryser for \(\cJ\) if and only if \(y(c_k)\leq x(\cJ,c_k)\) holds for all \(c_k\in C\).

If \(c_k=\phi(\lambda)\) then, as \(\xdk-2\edk\) and, by Lemma \[lem4290\], \(\edk=0\), it follows that \(\xdk=0\). Therefore, \(x(\cJ,c_k)=\xk\). Now, as \(y\) is Ryser for \(\cH\), it follows that \(\yk\leq x(\cJ,c_k)\) which means that \(y\) is Ryser for \(\cJ\).

If \(c_k\in C\backslash\{\phi(\lambda)\}\) then, as \(\xdk=2\edk-2\) it follows that \(x(\cJ,c_k)=2\edk-2+\xk\). By Lemma \[lem4290\] \(\edk\in\{0,1\}\). If \(\edk=1\) then \(x(\cJ,c_k)=\xk\) and therefore, as \(y\) is Ryser for \(\cH\), \(\yk\leq x(\cJ,c_k)\) follows. If \(\edk=0\) then \(x(\cJ,c_k)=\xk-2\) and so \(\yk\leq x(\cJ,c_k)\) holds if and only if \(\xk-y(c_k)\geq 2\).

Therefore \(\yk\leq x(\cJ,c_k)\) holds for all \(c_k\in C\) if and only if there is no colour \(c_k\in C\) with \(\xk-\yk<2\) and \(\edk=0\). In other words, if and only if \(\xk-\yk<2\) implies \(\edk=1\). If \(\xk-\yk<2\) then, as \(\xk\equiv\yk\bmod{2}\) and \(\xk\geq\yk\) it follows that \(\xk-\yk=0\). Therefore, \(y\) is admissible for \(\cJ\) if and only if, for every \(c_k\in C\backslash\{\phi(\lambda)\}\) with \(\xk-\yk=0\) it follows that \(\edk=1\).

\[lem4990\] If \(\eps\in F\) and \(y\) is a Ryser admissible complete loop assignment for \(\cH\) then an \(\eps\)-extension is \(y\)-compatible if and only if (\[lem49901\]), (\[lem49902\]) or (\[lem49903\]) holds for every \(c_k\in C\backslash\{\phi(\eps)\}\) which satisfies \(\xk-\yk=0\) and (\[lem49901\]), (\[lem49905\]) and (\[lem49906\]) holds for every \(c_k\in C\backslash\{\phi(\eps)\}\) which satisfies \(\xk-\yk=2\).

1. \(c_k=c_s=c_t\) \[lem49901\]

2. \(c_s\neq c_t\), \(c_k\in\{c_s,c_t\}\) and \(\edk=1\) \[lem49902\]

3. \(c_s\neq c_t\), \(c_k\notin\{c_s,c_t\}\) and \(\edk=2\) \[lem49903\]

4. \(c_s\neq c_t\), \(c_k\in\{c_s,c_t\}\) \[lem49905\]

5. \(\edk\geq 1\) \[lem49906\]

First it is shown that \(y'=y'(\phi(\eps),c_s,c_t)\) is an admissible complete loop assignment for \(\cJ\). Then it follows that \(\cJ\) is \(y\)-compatible if and only if \(y'\) is Ryser.

As \(\cJ\) is an \(\eps\)-extension it follows that \(F(\cJ)=F\backslash\{\eps\}\). By definition \(y'(C)=y'(C\backslash\{c_s,c_t\})+y'(\{c_s,c_t\})=y(C\backslash\{c_s,c_t\})+y(\{c_s,c_t\})-2=y(C)-2\). Therefore \(y'(C)=y(C)-2=2(|F|-1)=2(|F(\cJ)|)\) and hence \(y'\), by definition, is a complete loop assignment for \(\cJ\).

\(\cJ\) is admissible if and only if \(x(\cJ,c_k)\equiv y'(c_k)\bmod{2}\) for all \(c_k\in C\). By definition \(\xdk=2\edk+\ldk-(4+2\Edk+\Ldk)\equiv\ldk-\Ldk\bmod{2}\). If \(c_k\in\{c_s,c_t\}\) then, from Lemma \[lem4295\], it follows that \(\xdk\equiv 0\bmod{2}\) and so \(x(\cJ,c_k)\equiv\xk\bmod{2}\). Therefore, as \(y'(c_k)=\yk\) and \(\xk\equiv\yk\bmod{2}\) it follows that \(x(\cJ,c_k)\equiv y'(c_k)\bmod{2}\). If \(c_s\neq c_t\) and \(c_k\in\{c_s,c_t\}\) then, by Lemma \[lem4295\], \(\xdk\equiv 1\bmod{2}\) and, by definition, \(y'(c_k)=\yk-1\). Therefore \(x(\cJ,c_k)\equiv\xk+1\bmod{2}\) and so, as \(\xk\equiv\yk\bmod{2}\) it follows that \(x(\cJ,c_k)\equiv y'(c_k)\bmod{2}\). If \(c_k=c_s=c_t\) then, by Lemma \[lem4295\], \(\xdk\equiv 0\bmod{2}\) and so, as, by definition, \(y'(c_k)=\yk-2\) it follows that \(\xk\equiv y'(c_k)\bmod{2}\). Therefore \(y'\) is admissible for \(\cJ\).

Now \(\cJ\) is \(y\)-compatible if and only if \(y'\) is Ryser for \(\cJ\) and \(y'\) is Ryser for \(\cJ\) if and only if \(y'(c_k)\leq x(\cJ,c_k)\) holds for all \(c_k\in C\). If \(c_k=\phi(\eps)\) then, by Lemma \[lem4295\], it follows that \(\xdk=0\) and so \(x(\cJ,c_k)=\xk\). Therefore, as \(y'(c_k)=\yk\) and \(\yk\leq\xk\), it follows that \(y'(c_k)\leq\xk\).

If \(c_s\neq c_t\) and \(c_k\in\{c_s,c_t\}\) then, by Lemma \[lem4295\], it follows that \(\xdk=2\edk-3\). By definition \(y'(c_k)=\yk-1\) and so \(y'(c_k)\leq x(\cJ,c_k)\) holds if and only if \(\yk-1\leq 2\edk-3+\xk\) or \(\yk\leq 2\edk-2+\xk\). If \(\edk=1\) then this follows as \(y\) is Ryser. Otherwise, by Lemma \[lem4295\], \(\ldk=0\) and this expression holds if and only if \(\yk\leq\xk-2\). If \(\xk-\yk<2\) then, as \(\xk\equiv\yk\bmod{2}\) and \(\xk\geq\yk\) it follows that \(\xk-\yk=0\). Therefore, in this case, \(y'(c_k)\leq x(\cJ,c_k)\) holds if and only if there is no colour \(c_k\) with \(\xk-\yk=0\).

If \(c_k=c_s=c_t\) then, by Lemma \[lem4295\], it follows that \(\xdk=2\cdot 0+2-(4+2\cdot 0+0)=-2\) and so, as \(y'(c_k)=\yk-2\) it follows that \(y'(c_k)\leq x(\cJ,c_k)\) if and only if \(\yk-2\leq\xk-2\), in other words, if and only if \(y\) if Ryser.

If \(c_k\in C\backslash\{\phi(\eps),c_s,c_t\}\) then, by Lemma \[lem4295\], it follows that \(\xdk=2\edk+0-(4+2\cdot 0+0)=2\edk-4\). As \(y'(c_k)=\yk\) it follows that \(y'(c_k)\leq x(\cJ,c_k)\) if and only if \(\yk\leq 2\edk-4+\xk\). If \(\edk=2\) then this follows as \(y\) is Ryser. Otherwise, by Lemma \[lem4295\], \(\edk\in\{0,1\}\). If \(\edk=0\) then \(y'(c_k)\leq x(\cJ,c_k)\) if and only if \(\yk\leq\xk-4\) and if \(\edk=1\) then \(y'(c_k)\leq\xk\) if and only if \(\yk\leq\xk-2\). If \(\xk-\yk<4\) then, as \(\xk\equiv\yk\bmod{2}\) and \(\xk\geq\yk\) it follows that \(\xk-\yk\in\{0,2\}\) and if \(\xk-\yk<2\) it follows that \(\xk-\yk=0\). Therefore \(y'(c_k)\leq x(\cJ,c_k)\) if and only if \(c_k\) does not satisfy \(\xk-\yk\in\{0,2\}\) and \(\edk=0\) and does not satisfy \(\xk-\yk=0\) and \(\edk=1\).

Therefore \(y'\) is Ryser if and only if there is no colour \(c_k\) which satisfies \(c_k\in\{c_s,c_t\}\) (\(c_s\neq c_t\)), \(\edk=0\) and \(\xk-\yk=0\) or \(c_k\in\{\phi(\eps),c_s,c_t\}\), \(\xk-\yk=0\) and \(\edk=1\).

Therefore \(y'\) is Ryser if and only if every colour \(c_k\) which satisfies \(\xk-\yk=0\) satisfies (\[lem49901\]),(\[lem49902\]) or (\[lem49903\]) and every colour \(c_k\) which satisfies \(\xk-\yk=2\) satisfies (\[lem49901\]),(\[lem49905\]) or (\[lem49906\]).

Compatible pairs \[sec5000\] In this section the aims are to give necessary and sufficient conditions for an extension corresponding to a proper pair to be a \(y\)-compatible extension.

\[def5010\] If \(\lambda\in\Lambda\), \((S,\theta)\) is a \(\phi(\lambda)\)-proper pair and \(y\) is a Ryser admissible complete loop assignment for \(\cH\) then \((S,\theta)\) is a -compatible -proper pair if and only if the \(\lambda\)-extension corresponding \((S,\theta)\) is \(y\)-compatible.

\[lem5020\] If \(\lambda\in\Lambda\) and \(y\) is a Ryser admissible complete loop assignment for \(\cH\) then \((S,\theta)\) is \(y\)-compatible if and only if (\[lem50201\]) holds.

1. If \(\xk-\yk=0\) then \(c_k\in S\) for every \(c_k\in C\backslash\{\phi(\lambda)\}\). \[lem50201\]

By definition \((S,\theta)\) is \(y\)-compatible if and only if the \(\lambda\)-extension corresponding to \((S,\theta)\) is \(y\)-compatible. By Lemma \[lem4980\], the corresponding \(\lambda\)-extension is \(y\)-compatible if and only if \(\xk-\yk=0\) implies \(\edk=1\) for every \(c_k\in C\backslash\{\phi(\lambda)\}\). The result follows from Lemma \[lem4320\] which says that \(\edk=1\) if and only if \(c_k\in S\).

\[def5030\] If \(\eps\in F\) and \(\{(S,\theta_S,c_s),(T,\theta_T,c_t)\}\) is a \((\phi(\eps),c_s,c_t)\)-proper pair then \(\{(S,\theta_S,c_s),(T,\theta_T,c_t)\}\) is -compatible if and only if the \(\eps\)-extension corresponding to \(\{(S,\theta_S,c_s),(T,\theta_T,c_t)\}\) is \(y\)-compatible.

\[lem5040\] If \(\eps\in F\) and \(\{(S,\theta_S,c_s),(T,\theta_T,c_t)\}\) is \(\phi(\eps)\)-proper then \(\{(S,\theta_S,c_s),(T,\theta_T,c_t)\}\) is \(y\)-compatible if and only if (\[lem50401\]), (\[lem50402\]) or (\[lem50403\]) holds for every \(c_k\in C\backslash\{\phi(\eps)\}\) which satisfies \(\xk-\yk=0\) and either (\[lem50401\]), (\[lem50405\]) and (\[lem50406\]) holds for every \(c_k\in C\backslash\{\phi(\eps)\}\) which satisfies \(\xk-\yk=2\).

1. \(c_k=c_s=c_t\) \[lem50401\]

2. \(c_s\neq c_t\), \(c_k\in\{c_s,c_t\}\) and \(c_k\in S\cup T\) \[lem50402\]

3. \(c_s\neq c_t\), \(c_k\notin\{c_s,c_t\}\) and \(c_k\in S\cap T\) \[lem50403\]

4. \(c_s\neq c_t\), \(c_k\in\{c_s,c_t\}\) \[lem50405\]

5. \(c_k\in S\cup T\) \[lem50406\]

By definition \(\{(S,\theta_S,c_s),(T,\theta_T,c_t)\}\) is \(y\)-compatible if and only if the \(\eps\)-extension \(\cJ\) corresponding to \(\{(S,\theta_S,c_s),(T,\theta_T,c_t)\}\) is \(y\)-compatible. By Lemma \[lem4990\] \(\cJ\) is \(y\)-compatible if and only if (\[lem49901\]), (\[lem49902\]) or (\[lem49903\]) of Lemma \[lem4990\] hold for every \(c_k\in C\backslash\{\phi(\eps)\}\) which satisfies \(\xk-\yk=0\) and (\[lem49901\]), (\[lem49905\]) or (\[lem49906\]) holds for every \(c_k\in C\backslash\{\phi(\eps)\}\) which satisfies \(\xk-\yk=2\). From Lemma \[lem4357\] it follows that (\[lem49901\])-(\[lem49906\]) of Lemma \[lem4990\] holds if and only if the corresponding condition of this lemma holds.

Compatible graphs \[sec5045\]

In this section the aim is to characterise the proper graphs whose corresponding extension is \(y\)-compatible.

\[def5050\] If \(\lambda\in\Lambda\) and \(A\) is a \(\phi(\lambda)\)-proper graph then \(A\) is a -compatible -proper graph if and only if the \(\lambda\)-extension corresponding to \(A\) is \(y\)-compatible.

\[lem5060\] If \(\lambda\in\Lambda\) and \(A\) is a \(\phi(\lambda)\)-proper graph then \(A\) is \(y\)-compatible if and only if (\[lem50601\]) holds.

1. If \(\xk-\yk=0\) then \(d(A,c_k)=1\) for every \(c_k\in C\backslash\{\phi(\lambda)\}\). \[lem50601\]

By definition \(A\) is \(y\)-compatible if and only if the corresponding \(\lambda\)-extension \(\cJ\) of \(\cH\) is \(y\)-compatible. By Lemma \[lem5020\] \(\cJ\) is \(y\)-compatible if and only if \(c_k\in S\) for every \(c_k\in C\backslash\{\phi(\eps)\}\) which satisfies \(\xk-\yk=0\). The result follows from Lemma \[lem4320\] which says that \(d(A,c_k)=1\) if and only if \(c_k\in S\)

\[def5070\] If \(\eps\in F\) and \(A\) is a \((\phi(\eps),c_s,c_t)\)-proper graph then \(A\) is a -compatible -proper graph if and only if the \(\eps\)-extension corresponding to \(A\) is \(y\)-compatible.

\[lem5080\] If \(\eps\in F\) and \(A\) is a \((\phi(\eps),c_s,c_t)\)-proper graph then \(A\) is \(y\)-compatible if and only if (\[lem50801\]), (\[lem50802\]) or (\[lem50803\]) holds for every \(c_k\in C\backslash\{\phi(\eps)\}\) which satisfies \(\xk-\yk=0\) and (\[lem50801\]), (\[lem50805\]) or (\[lem50806\]) holds for every \(c_k\in C\backslash\{\phi(\eps)\}\) which satisfies \(\xk-\yk=2\).

1. \(c_k=c_s=c_t\) \[lem50801\]

2. \(c_s\neq c_t\), \(c_k\in\{c_s,c_t\}\) and \(d(A,c_k)\geq 1\) \[lem50802\]

3. \(c_s\neq c_t\), \(c_k\notin\{c_s,c_t\}\) and \(d(A,c_k)=2\) \[lem50803\]

4. \(c_s\neq c_t\), \(c_k\in\{c_s,c_t\}\) \[lem50805\]

5. \(d(A,c_k)\geq 1\) \[lem50806\]

By definition \(A\) is \(y\)-compatible if and only if the \(\eps\)-extension \(\cJ\) of \(\cH\) corresponding to \(A\) is \(y\)-compatible. By Lemma \[lem5040\] \(\cJ\) is \(y\)-compatible if and only if (\[lem50401\]), (\[lem50402\]) or (\[lem50403\]) of Lemma \[lem5040\] holds for every \(c_k\in C\backslash\{\phi(\eps)\}\) which satisfies \(\xk-\yk=0\) and (\[lem50401\]), (\[lem50405\]) or (\[lem50406\]) of Lemma \[lem5040\] holds for every \(c_k\in C\backslash\{\phi(\eps)\}\) which satisfies \(\xk-\yk-2\). The result follows from Lemma \[lem4357\] which says that \(d(A,c_k)=2\) if and only if \(c_k\in S\cap T\) and \(d(A,c_k)\geq 1\) if and only if \(c_k\in S\cup T\).

In fact, when it comes to compatible extensions the graphs of interest have an additional vertex \(v^{\eps}\) and edges with \(v^{\eps}\) as an end, with the purpose of keeping track of the loop-assignment.

\[def5130\] If \(\eps\in F\) then the loop-assignment multigraph corresponding to a -proper graph \(A\) is the multigraph \(P\) with vertex-set \(V(P)=V(A)\cup\{v^{\eps}\}\) and edge-set \(E(P)=E(A)\cup\{v^{\eps}c_k,\yk\,|\,c_k\in C\}\).

\[def5230\] If \(\eps\in F\) and \(\{c_s,c_t\}\subset C\) then a multigraph \(P\triangleleft Q(\cH,y)\) is a -proper loop assignment multigraph if and only if \(P\) is the loop-assignment multigraph corresponding to a \((\phi(\eps),c_s,c_t)\)-proper graph \(A\).

\[lem5240\] If \(\eps\in F\) then \(P\) is a \((\phi(\eps),c_s,c_t)\)-proper loop-assignment graph if and only if (\[lem52401\])-(\[lem52403\]) hold.

1. \(\Delta(P)=2\) \[lem52401\]

2. \(d(P,v)=2\) for all \(v\in V\cup\{v^{\eps}\}\) \[lem52402\]

3. \((\phi(\eps)\phi(\eps),1)\) \[lem52403\]

By definition \(P\) is a \((\phi(\eps),c_s,c_t)\)-proper loop-assignment graph if and only if there is a \((\phi(\eps),c_s,c_t)\)-proper graph \(A\) for which \(P\) is the corresponding loop-assignment graph. From the definition of corresponding loop-assignment multigraph it follows \(d(P,u)=d(A,u)\) for all \(u\in V(P)\backslash\{v^{\eps},c_s,c_t\}\), \(d(P,v^{\eps})\), \(d(P,c_k)=d(N,c_k)+1\) if \(c_s\neq c_t\) and \(c_k\in\{c_s,c_t\}\) and \(d(P,c_k)=d(A,c_k)+2\) if \(c_k=c_s=c_t\).

Suppose \(A\) is a \((\phi(\eps),c_s,c_t)\)-proper graph and \(P\) is the corresponding loop-assignment multigraph. Then, by Lemma \[lem4660\], \(d(A,c_k)\leq 1\) if \(c_s\neq c_t\) and \(c_k\in\{c_s,c_t\}\) and so, as \(d(P,c_k)=d(A,c_k)+1\) it follows that \(d(P,c_k)\leq 2\). If \(c_k=c_s=c_t\) then, again by Lemma \[lem4660\], \(d(A,c_k)=0\) and so, as \(d(P,c_k)=d(A,c_k)+2\), it follows that \(d(P,c_k)=2\). Now, as \(d(P,v^{\eps})=2\) and \(d(B,c_k)=d(A,c_k)\) for all \(c_k\in C\backslash\{v^{\eps},c_s,c_t\}\), it follows from Lemma \[lem4660\] that \(\Delta(P)=2\) and \(d(P,v)=2\) for all \(v\in V\cup\{v^{\eps}\}\) and \(d(P,v^{\lambda})=0\). By construction \(E(A)\subset E(P)\) therefore, as \(\Delta(P)=2\), \((c_kc_k,1)\in E(P)\).

If \(P\) satisifies (\[lem52401\])-(\[lem52403\]) let \(A\) be the corresponding graph. Then it follows, by definition, that \(d(A,u)=d(P,u)\) for all \(u\in V(A)\backslash\{c_s.c_t\}\), \(d(A,c_k)=d(P,c_k)-1\) if \(c_s\neq c_t\) and \(c_k\in\{c_s,c_t\}\) and \(d(A,c_k)=d(P,c_k)-2\) if \(c_k=c_s=c_t\). Therefore Lemma \[lem4660\] implies that \(P\) is \((\phi(\eps),c_s,c_t)\)-proper.

\[def5250\] If \(P\) is a \((\phi(\eps),c_s,c_t)\)-proper loop-assignment graph then \(P\) is Ryser if and only if there is a Ryser \((\phi(\eps),c_s,c_t)\)-proper graph \(A\) for which \(P\) is the corresponding loop-assignment graph.

\[lem5260\] If \(\eps\in F\) then a \((\phi(\eps),c_s,c_t)\)-proper loop-assignment graph \(P\) is Ryser if and only if (\[lem52601\])-(\[lem52603\]) hold.

1. If \(c_k\in C\backslash\{\phi(\eps),c_s,c_t\}\) is critical then \(d(P,c_k)=2\) and if \(c_k\in C\backslash\{\phi(\eps),c_s,c_t\}\) is semi-critical then \(d(P,c_k)\geq 1\) \[lem52601\]

2. If \(c_s\neq c_t\) and \(c_k\in\{c_s,c_t\}\) then \(\xk>0\) and if \(\xk=1,2\) then \(d(P,c_k)=2\) \[lem52602\]

3. If \(c_k=c_s=c_t\) then \(\xk\geq 2\) \[lem52603\]

Suppose \(P\) is a Ryser \((\phi(\eps),c_s,c_t)\)-proper. Then, by definition, there is a Ryser \((\phi(\eps),c_s,c_t)\)-proper graph \(A\) for which \(P\) is the corresponding loop-assignment multigraph. As \(N\) is \((\phi(\eps),c_s,c_t)\)-proper it follows, by definition, that \(P\) is \((\phi(\eps),c_s,c_t)\)-proper. Therefore \(P\) is Ryser if and only if \(A\) is Ryser. By Lemma \[lem4740\] \(A\) is Ryser if and only if (\[lem47402\])-(\[lem47404\]) of Lemma \[lem4740\] hold.

From the definition of corresponding loop-assignment graph it follows that \(d(P,u)=d(A,u)\) for all \(u\in V(P)\backslash\{v^{\eps},c_s,c_t\}\), \(d(P,v^{\eps})=2\) and \(d(P,c_k)=d(A,c_k)+1\) if \(c_s\neq c_t\) and \(c_k\in\{c_s,c_t\}\) and \(d(P,c_k)=d(A,c_k)+2\) if \(c_k=c_s=c_t\). Therefore, if \(c_k\in C\backslash\{\phi(\eps),c_s,c_t\}\) is critical it follows by Lemma \[lem4740\] that \(d(P,c_k)=d(A,c_k)=2\) and if \(c_k\in C\backslash\{\phi(\eps),c_s,c_t\}\) is semi-critical then \(d(P,c_k)=d(A,c_k)\geq 1\). If \(c_s\neq c_t\) and \(c_k\in\{c_s,c_t\}\) then, by Lemma \[lem4740\], \(\xk>0\) and, if \(\xk\in\{1,2\}\) then \(d(P,c_k)=d(A,c_k)+1=2\). Finally if \(c_k=c_s=c_t\) then \(\xk\geq 2\).

Now suppose \(P\) is \((\phi(\eps),c_s,c_t)\)-proper and satisfies (\[lem52601\])-(\[lem52603\]). Then, by definition, there is a \((\phi(\eps),c_s,c_t)\)-proper graph \(A\) for which \(P\) is the corresponding loop-assignment multigraph. Therefore \(d(A,u)=d(P,u)\) for all \(u\in V(A)\backslash\{c_s,c_t\}\), \(d(A,c_k)=d(P,c_k)-1\) if \(c_s\neq c_t\) and \(c_k\in\{c_s,c_t\}\) and \(d(A,c_k)=d(P,c_k)-2\) if \(c_k=c_s=c_t\). Therefore (\[lem52603\]) implies (\[lem47403\]) of Lemma \[lem4740\]. If \(c_s\neq c_t\) and \(c_k\in\{c_s,c_t\}\) then, by (\[lem52602\]), \(\xk>0\) and, if \(\xk\in\{1,2\}\) then \(d(A,c_k)=d(P,c_k)-1=1\). Finally, (\[lem52601\]) implies (\[lem47402\]) of Lemma \[lem4740\]. Therefore, by Lemma \[lem4740\], \(N\) is Ryser \((\phi(\eps),c_s,c_t)\)-proper and therefore, as \(P\) is the loop-assignment multigraph corresponding to \(A\), it follows, by definition, that \(P\) is Ryser \((\phi(\eps),c_s,c_t)\)-proper.

\[def5270\] If \(P\) is a \((\phi(\eps),c_s,c_t)\)-proper multigraph then \(P\) is admissible if and only if there is a \((\phi(\eps),c_s,c_t)\)-proper graph \(A\) for which \(P\) is the corresponding loop-assignment multigraph.

\[lem5280\] If \(\eps\in F\) then a \((\phi(\eps),c_s,c_t)\)-proper loop-assignment multigraph \(P\) is admissible if and only if \(\{c_s,c_t\}\) is an admissible pair of colours.

By definition \(P\) is admissible if and only if there is an admissible \((\phi(\eps),c_s,c_t)\)-proper graph \(A\triangleleft\BH\) for which \(P\) is the corresponding loop-assignment multigraph. By Lemma \[lem4800\] \(A\) is admissible if and only \(\{c_s,c_t\}\) is an admissible pair of colours. Therefore, by definition, \(P\) is admissible if and only if \(\{c_s,c_t\}\) is an admissible pair of colours.

\[def5290\] A \((\phi(\eps),c_s,c_t)\)-proper loop-assignment multigraph \(P\triangleleft Q(\cH,y)\) is -compatible if and only there is a \(y\)-compatible \((\phi(\eps),c_s,c_t)\)-proper graph \(A\triangleleft\BH\) for which \(P\) is the corresponding loop-assignment multigraph.

\[lem5300\] If \(\eps\in F\) then a \((\phi(\eps),c_s,c_t)\)-proper loop-assignment multigraph \(P\) is \(y\)-compatible if and only if (\[lem53001\]) and (\[lem53002\]) both hold.

1. If \(\xk-\yk=0\) then \(d(P,c_k)=2\) for every \(c_k\in C\backslash\{\phi(\eps)\}\). \[lem53001\]

2. If \(\xk-\yk=2\) then \(d(P,c_k)\geq 1\) for every \(c_k\in C\backslash\{\phi(\eps)\}\). \[lem53002\]

If \(P\) is \(y\)-compatible then, by definition, there is a \(y\)-compatible \((\phi(\eps),c_s,c_t)\)-proper graph \(A\triangleleft\BH\) for which \(P\) is the corresponding loop-assignment multigraph. If \(c_k\in C\backslash\{\phi(\eps)\}\) satisfies \(\xk-\yk=0\) then, by Lemma \[lem5080\], either \(c_k=c_s=c_t\), in which case \(d(P,c_k)=2\) because \((v^{\eps}c_k,2)\in E(P)\), or \(c_s\neq c_t\), \(c_k\in\{c_s,c_t\}\) and \(d(A,c_k)=1\) in which case \(d(P,c_k)=d(A,c_k)+1=2\) or \(c_s\neq c_t\), \(c_k\notin\{c_s,c_t\}\) and \(d(A,c_k)=2\) in which case \(d(P,c_k)=d(A,c_k)=2\). If \(c_k\in C\backslash\{\phi(\eps)\}\) satisfies \(\xk-\yk=2\) then, by Lemma \[lem5080\], either \(c_k=c_s=c_t\) in which case \(d(P,c_k)=2\) or \(c_s\neq c_t\) and \(c_k\in\{c_s,c_t\}\) in which case \(d(P,c_k)=d(A,c_k)+1\geq 1\) or \(d(A,c_k)\geq 1\) in which case \(d(P,c_k)\geq d(A,c_k)\geq 1\).

Now suppose \(P\) is a \((\phi(\eps),c_s,c_t)\)-proper loop-assignment multigraph which satisfies the lemma. Let \(A\) be the graph corresponding to \(P\). If \(c_k\in C\backslash\{\phi(\eps)\}\) satisfies \(\xk-\yk=0\) then \(d(P,c_k)=2\) and so, if \(c_k\notin\{c_s,c_t\}\) then \(d(A,c_k)=d(P,c_k)=2\). Otherwise, if \(c_k\in\{c_s,c_t\}\) either \(c_k=c_s=c_t\) or \(c_s\neq c_t\) and \(d(A,c_k)=d(P,c_k)-1=1\). If \(c_k\in C\backslash\{\phi(\eps)\}\) satisfies \(\xk-\yk=2\) then \(d(P,c_k)\geq 1\). If \(c_k\notin\{c_s,c_t\}\) then \(d(A,c_k)=d(P,c_k)\geq 1\), otherwise either \(c_k=c_s=c_t\) or \(c_s\neq c_t\). Therefore, by Lemma \[lem5080\] \(A\) is \(y\)-compatible therefore \(P\), which is the corresponding loop-assignment multigraph is \(y\)-compatiible.

Now suppose \(P\) is \(y\)-compatible. Then, by definition, there is a \(y\)-compatible graph \(A\) for which \(P\) is the corresponding loop-assignment multigraph. If \(c_k\in C\backslash\{\phi(\eps)\}\) and \(\xk-\yk=0\) then either \(c_k=c_s=c_t\), in which case \(d(P,c_k)=2\) as \((v^{\eps}c_k,2)\in E(P)\) by the definition of corresponding loop-assignment multigraph. If \(c_s=c_t\) and \(c_k\notin\{c_s,c_t\}\) then by Lemma \[lem5080\] (\[lem50803\]) it follows that \(d(P,c_k)=d(A,c_k)=2\). If \(c_s\neq c_t\) and \(c_k\in\{c_s,c_t\}\) then \(d(P,c_k)=d(A,c_k)+1=2\), by Lemma \[lem5080\] (\[lem50802\]). If \(\xk-\yk=2\) and \(c_k=c_s=c_t\) then \(d(P,c_k)=2\) because \((v^{\eps}c_k,2)\in E(P)\). If \(c_s\neq c_t\) and \(c_k\in\{c_s,c_t\}\) then \(d(P,c_k)=d(A,c_k)+1\geq 1\).. Otherwise \(c_k\notin\{c_s,c_t\}\) and \(d(P,c_k)=d(A,c_k)\geq 1\) by Lemma \[lem5080\] (\[lem50806\])

\[lem5310\] If \(\eps\in F\) then a multigraph \(P\triangleleft Q(\cH,y)\) is \((\phi(\eps),c_s,c_t)\)-proper, Ryser, admissible and \(y\)-compatible if and only if (\[lem53101\])-(\[lem53104\]) hold.

1. \(\Delta(P)=2\) \[lem53101\]

2. \((\phi(\eps)\phi(\eps),1)\in E(P)\) \[lem53102\]

3. \(v^{\eps}c_s\in E(P)\) and \(v^{\eps}c_t\in E(P)\) \[lem53103\]

4. If \(d(Q,u)=n-r\) then \(d(P,u)=2\) and if \(d(Q,c_k)=n-r-2\) then \(d(P,c_k)\geq 1\) \[lem53104\]

If \(P\) is \((\phi(\eps),c_s,c_t)\)-proper then (\[lem53101\])-(\[lem53102\]) follow from Lemma \[lem5240\]. Moreover, from (\[lem52402\]) of Lemma \[lem5240\] it follows that (\[lem53104\]) holds if and only if \(d(Q,c_k)=n-r\) implies \(d(P,c_k)=2\) and \(d(Q,c_k)=n-r-2\) implies \(d(P,c_k)\geq 1\). This, as is shown next, follows if and only if \(P\) admissible and \(y\)-compatible.

If \(c_k\in C\backslash\{\phi(\eps)\}\) and \(d(Q,c_k)=n-r\) then, because \(d(Q,c_k)=(n-r)-\xk+\yk\), it follows that \(\yk-\xk=0\) in which case, by Lemma \[lem5300\], it follows that \(d(P,c_k)=2\). If \(d(Q,c_k)=n-r-2\) then by the same reasoning \(\yk-\xk=2\) and by Lemma \[lem5300\] it follows that \(d(P,c_k)\geq 1\).

Now suppose \(P\triangleleft Q(\cH,y)\) satisfies (\[lem53101\])-(\[lem53104\]). Then, by Lemma \[lem5240\], \(P\) is \((\phi(\eps),c_s,c_t)\)-proper. \(P\) is \(y\)-compatible because, if \(c_k\in C\backslash\{\phi(\eps)\}\) satisfies \(\xk-\yk=0\) then, because \(d(Q,c_k)=(n-r)-\xk+\yk\), it follows that \(d(Q,c_k)=n-r\) and so, by Lemma \[lem5300\], \(d(P,c_k)=2\). Similarly, if \(c_k\in C\backslash\{\phi(\eps)\}\) satisfies \(\xk-\yk=2\), then \(d(Q,c_k)=n-r-2\) and so \(d(P,c_k)\geq 1\) by Lemma \[lem5300\].

Finally \(P\) is admissible because \(\{c_s,c_t\}\) is an admissible pair of colours.

Compatible decompositions \[sec5320\] Up to this point the focus has been on finding necessary and sufficient conditions for \(\cH\) to have a compatible Ryser admissible extension. The motivation for this focus is Lemma \[lem4970\] which says that if \(\cH\) can be embedded in a proper \(C\)-edge-coloured \(r\)-free-type complete graph \(\cK\) then the restriction of \(\cK\) to an extension is a compatible Ryser admissible extension. However, much as in Chapter 2, something much stronger is obviously true. If \(\cH\) is \(y\)-embeddable then for every free-loop and free-edge \(\mu\in F\cup\Lambda\) there is a \(y\)-compatible Ryser admissible proper \(\mu\)-extension, and for any pair \(\mu,\mu'\) the \(\mu\) and \(\mu'\) extensions are “compatible” in the other sense that if \(uv\) and \(uw\), with \(u\in V\), \(v\) an end of \(\mu\) and \(w\) and end of \(\mu'\), then \(uv\) and \(uw\) must be coloured differently.

\[def5330\] A \(C\)-edge-coloured \(r\)-free-type graph \(\cH\) of order \(n\) is -semi-embeddable if and only if \(\cH\) can be embedded in a proper \(C\)-edge-coloured graph \(\cK=(K,(C,\psi)\), where \(K=H\cdot (F\cup\Lambda)\), in such a way that the restriction \(\cK|_J\) of \(\cK\) to a subgraph \(J=H\cdot\mu\) for \(\mu\in F\cup\Lambda\) is a \(y\)-compatible Ryser admissible proper \(\mu\)-extension of \(\cH\).

\[lem5340\] If a proper \(C\)-edge-coloured \(r\)-free-type graph \(\cH\) of order \(n\) can be embedded in proper \(C\)-edge-coloured complete graph of order \(n\) then \(\cH\) is \(y\)-semi-embeddable for some Ryser admissible complete loop assignment \(y\).

Suppose that \(y\) is Ryser admissible complete loop assignment and \(\cH\) is \(y\)-embeddable. Then, because \(\cJ(\mu)=\cK|_{H\cdot\mu}\) is a \(y\)-embeddable proper \(\mu\)-extension of \(\cH\) for every \(\mu\in F\cup\Lambda\), it follows by Lemma \[lem4040\] that \(\cJ(\mu)\) is Ryser and by Lemma \[lem4060\] that \(\cJ(\mu)\) is admissible for every \(\mu\in F\cup\Lambda\).

If \(\mu\in L\) then \(\cJ=\cJ(\mu)\) is \(y\)-embeddable and if \(\mu\in F\) then \(\cJ\) is \(y'\)-embeddable. Therefore, by Lemma \[lem4880\], if \(\mu\in L\) then \(y\) is a Ryser admissible complete loop-assignment for \(\cJ\) and if \(\mu\in F\) then \(y'\) is a Ryser admissible complete loop-assignment for \(\cJ\). It follows, by definition, that \(\cJ\) is \(y\)-compatible. Therefore \(\cJ(\mu)\) is \(y\)-compatible for all \(\mu\in F\cup\Lambda\).

The property of being \(y\)-semi-embeddable is reflected in \(Q(\cH,y)\) having a decomposition into compatible subgraphs.

\[def5350\] A decomposition \(\cQ\) of \(Q(\cH,y)\) is -compatible if and only if \(\cQ=\{Q_i\,|\,i\in [|F|+|\Lambda|]\}\) and (\[def53501\]) and (\[def53502\]) both hold.

1. If \(F=\{\eps_i\,|\, i\in [|F|]\}\) then \(Q_i\) is a \(y\)-compatible Ryser admissible \((\phi(\eps_i),c_s,c_t)\)-proper loop-assignment multigraph for all \(i\in [|F|]\). \[def53501\]

2. If \(L=\{\lambda_i\,|\, i\in[|\Lambda|]\}\) then \(Q_i\) is a \(y\)-compatible Ryser admissible \(\phi(\lambda_i)\)-proper graph for all \(i\in [|F|+|\Lambda|]\backslash [|F|]\). \[def53502\]

\[lem5360\] \(\cH\) is \(y\)-semi-embeddable if and only if \(Q(\cH,y)\) has a \(y\)-compatible decomposition.

If \(\cH\) is \(y\)-semi-embeddable then, by definition, \(\cH\) can be embedded in a proper \(C\)-edge-coloured graph \(\cK=(K,(C,\psi))\), where \(K=H\cdot(F\cup\Lambda)\), in such a way that the restriction of \(\cK\) to a \(\mu\)-extension \(\cJ(\mu)=\cK|_{H\cdot\mu}\) is a \(y\)-compatible Ryser admissible proper \(\mu\)-extension of \(\cH\).

If \(\mu\in\Lambda\) then by definition there is a \(y\)-compatible Ryser admissible \(\phi(\mu)\)-proper pair \((S,\theta)_{\mu}\) corresponding to \(\cJ(\mu)\) and, also by definition, there is a \(y\)-compatible Ryser admissible \(\phi(\mu)\)-proper graph \(P(\mu)\triangleleft Q=Q(\cH,y)\) corresponding to \((S,\theta)_{\mu}\).

If \(\mu\in F\) then, by definition, there is a \(y\)-compatible Ryser admissible \((\phi(\mu),c_s,c_t)\)-proper pair \(\{(S,\theta_S,c_s),(T,\theta_T,c_t)\}_{\mu}\) corresponding to \(\cJ(\mu)\) and also, by definition, there is a corresponding \(y\)-compatible Ryser admissible \((\phi(\mu),c_s,c_t)\)-proper graph \(P(\mu)\triangleleft Q\) corresponding to \(\{(S,\theta_S,c_s),(T,\theta_T,c_t)\}_{\mu}\).

Now suppose that \(Q\) has a \(y\)-compatible decomposition \(\cQ\). By definition, there is a \(y\)-compatible Ryser admissible \(\phi(\lambda)\)-proper graph for every \(\lambda\in\Lambda\) and a \(y\)-compatible Ryser admissible \((\phi(\eps),c_s,c_t)\)-proper graph for every \(\eps\in F\). If all these extensions are performed simultaneously then the resulting edge-coloured graph proves that \(\cH\) is \(y\)-semi-embeddable.

Compatible edge-colourings \[sec5370\] In this section the aim is to characterise those edge-colourings of \(Q(\cH,y)\) which induce compatible decompositons of \(Q(\cH,y)\).

\[def5380\] If \(T\subseteq S\) then an \(S\)-edge-coloured multigraph \(\cG=(G,\theta)\) is -equalised if and only if \(||[\cG,s]|-|[\cG,t]||\leq 1\) for all \(\{s,t\}\subseteq T\).

\[def5390\] If \(T\subset S\) and \(m\in\bf{N}\) then an \(S\)-edge-coloured multigraph \(\cG\) is -equitable if and only if \(|d(\left\langle \cG,s \right\rangle,u)-d(\left\langle \cG,t \right\rangle,u)|\leq 1\) for all \(\{s,t\}\subseteq T\) and vertices \(u\in V(G)\) which satisfy \(d(G,u)=m\).

\[def5395\] If \(T\subset S\) and \(m\in\bf{N}\) then an \(S\)-edge-coloured multigraph \(\cG\) is -bounded if and only if \(|d(\left\langle \cG,s \right\rangle,u)|\leq m\) for all \(s\in T\) and vertices \(u\in V(G)\).

\[def5400\] An \(S\)-edge-colouring \(\rho\) of \(Q=Q(\cH,y)\) is a -compatible -edge-colouring of if and only if \(\{\left\langle(Q,(S,\rho)),s\right\rangle\,|\, s\in S\}\) is a \(y\)-compatible decomposition of \(Q\).

\[lem5410\] An \(S\)-edge-colouring \(\rho\) of \(Q(\cH,y)\) is \(y\)-compatible if and only if \(|S|=|F|+|\Lambda|\) and (\[lem54101\]), (\[lem54102\]), (\[lem54103\]) and (\[lem54104\]) hold.

1. \(\rho\) is \((S_F,2)\)-bounded and \((S_L,1)\)-bounded. \[lem54101\]

2. \(\rho\) is \(S_F\)-equalised. \[lem54102\]

3. \(\rho\) is \((S_F,n-r-2)\) equitable. \[lem54103\]

4. \(d(\left\langle Q,s\right\rangle,v^{\eps})=2\) for all \(s\in S_F\) and \(d(\left\langle Q,s\right\rangle,v^{\lambda})=1\) for all \(s\in S_L\). \[lem54104\]

Where \(S=\{s_i\,|\, i\in[|F|+|\Lambda|]\}\), \(S_{F}=\{s_i\,|\,i\in [|F|]\}\) and \(S_{\Lambda}=S\backslash S_{F}\).

First suppose \(\rho\) is \(y\)-compatible. Then, by definition, the decomposition \(\{\left\langle(Q,(S,\rho)),s\right\rangle\,|\, s\in S\}\) of \(Q\) is \(y\)-compatible. Therefore, \(k=|F|+|\Lambda|\) and \(Q_i=\left\langle(Q,(S,\rho)),s_i\right\rangle\) is a \(y\)-compatible Ryser admissible \((\phi(\eps),c_s,c_t)\)-proper loop-assignment multigraph for all \(i\in [|F|]\) and a \(y\)-compatible Ryser admissible \(\phi(\lambda)\)-proper graph for \(i\in [|\Lambda|]\backslash [|F|]\).

By Lemma \[lem5310\] \(\Delta(Q_i)=2\) for all \(i\in [|F|]\) and, by Lemma \[lem4610\] \(\Delta(Q_i)=1\) for all \(i\in [|\Lambda|]\backslash [|F|]\). Therefore \(\rho\) is \((S_F,2)\)-bounded and \((S_{\Lambda},1\})\)-bounded.

Lemma \[lem5240\] implies that \(|E(Q_i)|=2r+3\) for all \(i\in [|F|]\). Therefore \(|E(Q_i)|-|E(Q_j)|=0\) for all \(\{i,j\}\in [|F|]\) and so \(\rho\) is \(S_F\)-equalised.

If \(d(Q,u)=n-r-2\) then, by Lemma \[lem5310\] (\[lem53104\]) it follows that, if \(i\in [|F|]\), then \(d(Q_i,c_k)\geq 1\). As \(\Delta(Q_i)= 2\) it follows that \(d(Q_i,c_k)\in\{1,2\}\). Therefore \(|d(Q_i,c_k)-d(Q_j,c_k)|\leq 1\) for all \(1\leq i,j\leq |F|\), hence \(\rho\) is \((S_F,n-r-2)\)-equitable.

Now suppose \(k=|F|+|\Lambda|\) and \(\rho\) satisfies (\[lem54101\])-(\[lem54104\]). Let \(\cQ=\{\left\langle(Q,(S,\rho)),s\right\rangle\,|\, s\in S\}\) and \(Q_i=\left\langle(Q,(S,\rho)),s_i\right\rangle\)

If \(i\in [|F|]\) then, as \(\rho\) is \((S_F,2)\)-bounded it follows that \(\Delta(Q_i)=2\) if there is a vertex \(u\in V(Q_i)\) with \(d(Q_i,u)=2\). If \(u\in V\) then \(d(Q,u)=n-r\) and so, as \(2|F|+|\Lambda|=n-r\) it follows that \(d(Q_i,u)=2\).

As \(\rho\) is \((S_L,1)\)-bounded it follows that, if \(\lambda\) is any loop of \(Q\) then \(\rho(\lambda)\in S_F\). As \(\rho\) is \(S_F\)-equalised and \(Q\) has exactly \(|F|\) loops it follows that there is exactly one loop of every colour in \(S_F\).

If \(F=\{\eps_i\,|\,i\in [|F|]\}\) then let the \(Q_i\) be labelled such that \(\phi(\eps_i)\phi(\eps_i)\) has colour \(Q_i\) for all \(i\in [|F|]\).

By Lemma \[lem5240\] \(d(Q_i,v^{\eps})=2\) for all \(i\in [|F|]\).

Finally, if \(d(Q,u)=n-r\) then \(d(Q_i,u)=2\) follows as \(2|F|+|\Lambda|=n-r\) and, because \(\rho\) is \((S_F,n-r-2)\)-equitable it follows that \(d(D_i,u)\geq 1\).

Therefore \(Q_i\in\cQ\) is a \(y\)-compatible Ryser admissible \(\phi(\eps_i)\)-proper supergraph for all \(i\in [|F|]\).

If \(i\in [|\Lambda|]\backslash [|F|]\) then, as \(\rho\) is \((S_{\Lambda},1)\)-bounded it follows, as \(2|F|+|\Lambda|=n-r\) that \(\Delta(Q_i)=1\) and \(d(Q_i,u)=1\) if \(d(Q,u)=n-r\). Therefore, as \(d(Q_i,v^{\lambda})=1\), \(Q_i\) is \(y\)-compatible Ryser admissible \(\phi(\lambda)\)-proper.

It follows by definition that \(\cQ\) is a \(y\)-compatible decomposition.

\[cor5415\] If \(L=\emptyset\) then an \(S\)-edge-colouring \(\rho\) of \(Q(\cH,y)\) is \(y\)-compatible if and only if \(|S|=(n-r)/2\) and (\[lem54151\]), (\[lem54152\]), (\[lem54153\]) and (\[lem54154\]) hold.

1. \(\rho\) is \(2\)-bounded. \[lem54151\]

2. \(\rho\) is equalised. \[lem54152\]

3. \(\rho\) is \(n-r-2\) equitable. \[lem54153\]

Results \[sec5420\] In this section the ultimate aim is to prove Theorem \[thm5550\] which characterises embeddable proper \(C\)-edge-coloured \(r\)-free-type graphs with no free-loops. Prior to this the unembeddable Ryser admissible proper \(C\)-edge-coloured \(r\)-free-type graphs with no free-loops are described in Definition \[def5510\] and Definition \[def5530\]

\[def5500\] A subset \(S\subseteq C\) is -bad if and only if (\[def55001\]), (\[def55002\]) and (\[def55003\]) hold.

1. \(\eps(S)=(k-2)/2\) \[def55001\]

2. \(r|S|-(2e(S)+l(S))=k(|S|-j)\) \[def55002\]

3. \(|N(S)|=|S|-j\) \[def55003\]

\[def5510\] A Ryser admissible proper \(C\)-edge-coloured \(r\)-free-type graph \(\cH\) of order \(n\) is Type 1 if and only if \(L=\emptyset\), \(o(\cH)=n-r\) and either (\[def55101\]) or (\[def55102\]) holds.

1. \(C\) contains a \((2,n-r)\)-bad subset \(S\) such that \(O(\cH)\subseteq S\). \[def55101\]

2. \(C\) contain a \((1,n-r)\)-bad subset \(S\) such that \(O(\cH)\cap S=\emptyset\). \[def55102\]

\[def5530\] A Ryser admissible proper \(C\)-edge-coloured \(r\)-free-type graph \(\cH\) of even order \(n\) is Type 2 if and only if \(L=\emptyset\), \(o(\cH)=n-r-2\) and either (\[def55301\]) or (\[def55302\]) holds.

1. \(n-r=4\) and \(C\) contains \((j,n-r)\)-bad sets \(S\) and \(T\) such that \(O(\cH)\cap S=O(\cH)\cap T=\emptyset\) and \(j\in\{1,2\}\)\[def55301\]

2. \(n-r\geq 6\) and \(C\) contains a \((1,n-r)\)-bad set \(S\) such that \(S\cap O(\cH)=\emptyset\) and a set \(T\) such that (\[def55303\])-(\[def55306\]) hold.

   1. \(\eps(T)=0\) \[def55303\]

   2. \(r|T|-2e|T|=(|T|-1)(n-r)\) \[def55304\]

   3. \(|N(T)|=|T|-1\) \[def55305\]

   4. \(O(\cH)\subseteq T\) \[def55306\]

   \[def55302\]

\[lem5540\] If \(\cH\) is a Ryser admissible proper \(C\)-edge-coloured \(r\)-free-type graph of order \(n\), \(L=\emptyset\) and \(y\) is a Ryser admissible complete loop-assignment for \(\cH\) then \(\cH\) is \(y\)-semi-embeddable if and only if every component of \(Q(\cH,y)\) is \((n-r)\)-good.

By Lemma \[lem5360\] \(\cH\) is \(y\)-semi-embeddable if and only if \(Q=Q(\cH,y)\) has a \(y\)-compatible decomposition. By definition \(Q\) has a \(y\)-compatible decomposition if and only if \(Q(\cH,y)\) has a \(y\)-compatible \(S\)-edge-colouring. Now, by Lemma \[lem4925\], \(Q\) is an \((r+1,n)\)-\(B\)-type multigraph. Moreover a \(y\)-compatible decomposition of \(Q\) is a Ryser proper-type decomposition. Therefore, by Lemma \[lem3060\], \(Q\) has a \(y\)-compatible decomposition if and only if every component of \(Q\) is \((n-r)\)-good.

\[lem5545\] If \(\cH\) is a Ryser admissible proper \(C\)-edge-coloured \(r\)-free-type graph of order \(n\) and \(y\) is a Ryser admissible complete loop-assignment for \(\cH\) then \(\cH\) is \(y\)-embeddable if and only if \(\cH\) is \(y\)-semi-embeddable

The necessity follows directly from Lemma \[lem5340\]. To prove the sufficiency suppose that \(\cH\) is \(y\)-semi-embeddable and that the sufficiency holds for every Ryser admissible proper \(C\)-edge-coloured \(r'\)-free-type graphs of order \(n\), where \((n-r')/2<(n-r)/2\).

By Lemma \[lem5360\] \(Q=Q(\cH,y)\) has a \(y\)-compatible decomposition \(\cQ\). Therefore, if \(\eps\in F\), it follows that there is a Ryser admissible \(\phi(\eps)\)-proper subgraph \(A\in\cQ\). Let \(\cJ\) be the corresponding \(y\)-compatible Ryser admissible proper \(\eps\)-extension of \(\cH\). If \(\cJ\) is \(y\)-semi-embeddable then, by induction, \(\cH\) is \(y\)-embeddable. Otherwise, by Lemma \[lem5540\], \(Q\) has an \((n-r)\)-bad component. Therefore, as \(Q\) is \((r+1,n)\)-\(B\)-type it follows from Lemma \[lem3230\] and Lemma \[lem3254\] that \(n-r\geq 8\) and \(S(\cJ)\) is \((n-r)\)-bad. By Lemma \[lem3256\] there exists a, possibly different, \(y\)-compatible decomposition \(\cQ'\neq\cQ\) with the property that, for some \(A'\in\cQ'\) and provisional decomposition \(\cA'\) of \(A'\) such that \(S(A',\cA',v_{r+1},v_{r+2})\) is \((n-r-2)\)-good. Therefore as \(T(A',\cA',v_{r+1},,v_{r+2})\) is, by Lemma \[lem3230\], \((n-r-2)\)-good it follows that the \(y\)-compatible Ryser admissible extension of \(\cH\) corresponding to \((A',\cA')\) is \((n-r-2)\)-good. Therefore \(\cH\) is \(y\)-embeddable by induction.

\[def5546\] Let \(y_1\) be defined by \(y_1(c_k)=1\) if and only if \(c_k\in O(\cH)\) and \(y_1(c_k)=0\) for all \(c_k\in C\backslash O(\cH)\).

\[lem5547\] If \(o(\cH)\in\{n-r,n-r-2\}\) and \(C\) contains a \((1,n-r)\)-bad set \(S\) with \(O(\cH)\cap S=\emptyset\) then \(Q(\cH,y_1)\) contains an \((n-r)\)-bad component \(\Lambda\) with \(V(\Lambda)\subseteq S\cup N(S)\). If \(O(\cH)=n-r\) and \(C\) contains a \((2,n-r)\)-bad set \(S\) with \(O(\cH)\subseteq S\) then \(Q(\cH,y_1)\) contains an \((n-r)\)-bad component \(\Lambda\) with \(V(\Lambda)\subseteq S\cup N(S)\cup\{v^{\eps}\}\).

Suppose \(S\subset C\) is \((j,n-r)\)-bad for some \(j\in\{1,2\}\) and, if \(j=1\), then \(O(\cH)\cap S=\emptyset\) and, if \(j=2\), then \(O(\cH)\subset S\). Let \(Q=Q(\cH,y_1)\). Then, because \(d(Q,c_k)=d(B,c_k)+y_1(c_k)=(n-r)-\xk+y_1(c_k)\) it follows, from the definition of \(\xk\) as \(\Lk=0\) for all \(c_k\in C\), that \[d(Q,c_k)=(n-r)-(2\ek+\lk-(2r-n+2\Ek))+\yk\] Therefore \[d(Q,S)=r|S|-(2e(S)+l(S)-2\eps(S))+y_1(S)\] Now, as \(S\) is \((j,n-r)\)-bad it follows that \(d(Q,S)=(n-r)(|S|-j)+(n-r-2)+y(S)\). If \(j=1\) and \(O(\cH)\cap S=\emptyset\) it follows that \(y(S)=0\) and \(d(Q,S)=(n-r)(|S|-1)+(n-r-2)\) and if \(j=2\) then \(O(\cH)\subseteq S\) it follows that \(y(S)=n-r\) and \(d(Q,S)=(n-r)(|S|-2)+(n-r-2)+(n-r)=(n-r)(|S|-1)+(n-r-2)\). It follows, in either case, that there exists \(c_k^{\star}\in C\) such that \(d(Q,c_k)=n-r\) for all \(c_k\in S\backslash\{c_k^{\star}\}\) and \(d(Q,c_k^{\star})=n-r-2\). Now, because \(|N(S)|=|S|-j\) and \(\eps(S)=(n-r-2)/2\) it follows that every non-loop edge with an end in \(S\) also has an end in \(N(S)\). It follows that the component \(\Gamma\) of \(Q\) containing \(c_k^{\star}\) is an \((n-r)\)-bad component. Moreover if \(j=1\) then \(V(\Gamma)\subseteq S\cup N(S)\) and, if \(j=2\), then \(V(\Gamma)\subseteq S\cup N(S)\cup\{v^{\eps}\}\).

\[thm5550\] If \(\Lambda=\emptyset\) then a Ryser admissible proper \(C\)-edge-coloured \(r\)-free-type graph of order \(n\) can be embedded in some proper \(C\)-edge-coloured complete graph of order \(n\) if and only if \(\cH\) is not Type 1 nor Type 2.

If \(\cH\) is Type 1 then \(o(\cH)=n-r\). By Lemma \[lem5547\] \(Q(\cH,y_1)\) contains an \((n-r)\)-bad component. Therefore, by Lemma \[lem5540\], \(\cH\) is not \(y_1\)-embeddable. It follows, as \(y_1\) is the only Ryser admissible complete loop assignment for \(\cH\), that \(\cH\) is not embeddable.

If \(\cH\) is Type 2 and \(n-r=4\) then there exist two \((j,n-r)\)-bad sets \(S\) and \(T\) with \(j(S)=1\) and \(j(T)=2\) or \(j(S)=j(T)=1\) such that \(O(\cH)\cap S=O(\cH)\cap T=\emptyset\). If \(j(S)=j(T)=1\) then by Lemma \[lem5547\] it follows that \(Q(\cH,y_1)\) contains two \((n-r)\)-bad components \(\Gamma_1\) and \(\Gamma_2\) say. Now, because at least one component of \(\{\Gamma_1,\Gamma_2\}\) is also a component of \(Q(\cH,y)\) for every Ryser admissible complete loop-assignment \(y\) it follows that \(\cH\) is not embeddable. If \(j(S)=1\) and \(j(T)=2\) then, by Lemma \[lem5547\], \(Q(\cH,y_1)\) contains exactly 1 \((n-r)\)-bad component \(\Gamma_1\) say. Now, \(\Gamma_1\) is a component of \(Q(\cH,y)\) unless \(y(c_k^{\star})=2\), where \(c^{\star}\) is the unique vertex in \(V(\Gamma_1)\) satisfying \(d(Q,c^{\star})=n-r-2\). However, if \(y(c^{\star})=2\) then, because \(v^{\eps}\) is a vertex of a component \(\Gamma_2\) with \(|V(\Gamma_2)\cap V|=|V(\Gamma_2)\cap C|\) it follows that \(Q(\cH,y)\) again contains an \((n-r)\)-bad component. So for every Ryser admissible complete loop-assignment \(y\) the multigraph \(Q(\cH,y)\) has an \((n-r)\)-bad component. Therefore \(\cH\) is not embeddable.

If \(\cH\) is Type 2 and \(n-r\geq 6\) then, by Lemma \[lem5547\] \(Q(\cH,y_1)\) contains an \((n-r)\)-bad component \(\Gamma_1\), say. Again \(\Gamma_1\) is an \((n-r)\)-bad component of \(Q(\cH,y)\) unless \(y(c^{\star})=2\), where \(c^{\star}\) is the unique vertex of degree \(n-r-2\) in \(V(\Gamma_1)\). However, if \(y(c^{\star})=2\) then, because \(v^{\eps}\) is a vertex of a component \(\Gamma_2\) with \(|V(\Gamma_2)\cap V|=|V(\Gamma_2)\cap C|\) it follows that \(Q(\cH,y)\) contains an \((n-r)\)-bad component. Therefore, for every Ryser admissible complete loop-assignment \(y\), \(Q(\cH,y)\) contains an \((n-r)\)-bad component. It follows that \(\cH\) is not embeddable.

Now the sufficiency is proved in three steps. The first step involves showing that if \(o(\cH)\leq n-r-4\) then there exists a Ryser admissible complete loop-assignment \(y\) for \(\cH\) such that \(Q(\cH,y)\) has no \((n-r)\)-bad component. Therefore, by Lemma \[lem5540\] and Lemma \[lem5547\], it follows that \(\cH\) is \(y\)-embeddable. The second step shows that if \(o(\cH)=n-r-2\) and \(\cH\) is not Type 2 then there exists a Ryser admissible complete loop-assignment \(y\) for \(\cH\) such that \(Q(\cH,y)\) has no \((n-r)\)-bad component. Again it follows that \(\cH\) is \(y\)-embeddable. Finally it is shown that if \(o(\cH)=n-r\) and \(\cH\) is not Type 1 then there exists a Ryser admissible complete loop-assignment \(y\) such that \(Q(\cH,y)\) has no \((n-r)\)-bad component. Again \(\cH\) is \(y\)-embeddable.

If \(o(\cH)\leq n-r-4\) then let \(y\) be any Ryser admissible complete loop-assignment for \(\cH\). If \(Q=Q(\cH,y)\) has no \((n-r)\)-bad component then, by Lemma \[lem5540\] and Lemma \[lem5547\], it follows that \(\cH\) is \(y\)-embeddable. If \(n-r=4\) and \(Q\) has a bad component it follows that exactly two components, \(\Gamma_1\) and \(\Gamma_2\) say, have loops. Therefore there exist vertices \(c_k\in V(\Gamma_1)\) and \(c_k'\in V(\Gamma_2)\) such that \(d(Q,c_k)\leq n-r-2\) and \(d(Q,c_k')\leq n-r-2\). If \(y''\) is defined by \(y''(c_k)=y''(c_k')=2\) it follows that both loops are contained in the same component of \(Q(\cH,y'')\). Therefore every component of \(Q(\cH,y'')\) is \((n-r-2)\)-good.

If \(n-r\geq 6\) then \(Q(\cH,y)\) has at most one \((n-r)\)-bad component. Hence if \(Q(\cH,y)\) has an \((n-r)\)-bad component it has exactly one. As \(Q(\cH,y)\) has exactly two components with loops it follows that \(Q=Q(\cH,y')\) has at most four and at least two.

If four components of \(Q\) have loops and \(v^{\eps}\) is not a vertex of any of them then let \(A\) and \(B\) be two such components and let \(c_A\in V(A)\) and \(c_B\in V(B)\) be vertices of degree at most \(n-r-2\). If \(y''\) is defined by \(y''(c_k)=y'(c_k)\) for all \(c_k\in C\backslash\{c_A,c_B\}\) then at least three components of \(Q''=Q(\cH,y'')\) have loops. Therefore every component of \(Q''\) is \((n-r)\)-good.

If four components of \(Q\) have loops and \(v^{\eps}\in V(A)\) then observe that some component of \(Q\) contains a vertex of degree \(\leq n-r-4\) or two vertices both of degree \(\leq n-r-2\). In the first case, if \(d(Q,c_k)\leq n-r-4\) put \(y''(c_k)=4\) and in the latter case, if \(d(Q,c_k)\leq n-r-2\) and \(d(Q,c_k')\leq n-r-2\) put \(y''(c_k)=y''(c_k)=2\). In either case every component of \(Q(\cH,y'')\) is \((n-r)\)-good because at least three different components of \(Q(\cH,y'')\) contain loops.

If exactly three components of \(Q\) have loops and \(v^{\eps}\) is not a vertex of any such component observe that the component containg \(v^{\eps}\) has a vertex \(c_k\) of degree \(\leq n-r-2\). Put \(y''(c_k)=y''(c_A)=2\), where \(c_A\) is a vertex of degree \(\leq n-r-2\) in component \(A\) containing a loop and not containing \(v^{\eps}\). Then every component of \(Q(\cH,y'')\) is \((n-r)\)-good because at least three different components of \(Q''\) contain loops. If \(v^{\eps}\in V(A)\) then put \(y''(c_B)=y''(c_C)=2\), where \(c_B\) and \(c_C\) are vertices of degree \(\leq n-r-2\) in components \(C_B\neq C_A\) and \(C_C\neq C_A\) respectively. Then exactly one component of \(Q''\) has loops. Again it follows that every component of \(Q''\) is \((n-r)\)-good.

If exactly two components \(A\) and \(B\) of \(Q\) have loops put \(y''(c_A)=y''(c_B)=2\), where \(c_A\) and \(c_B\) are vertices of \(A\) and \(B\) respectively of degree \(\leq n-r-2\). Then exactly one component of \(Q''\) contains loops and so every component of \(Q''\) is \((n-r)\)-good.

Now suppose that \(o(\cH)=n-r-2\). If \(n-r=4\) and \(Q(\cH,y)\) contains an \((n-r)\)-bad component then \(Q(\cH,y_1)\) has two components \(\Gamma_1\), \(\Gamma_2\) containing loops, each containing exactly one loop. If \(O(\cH)\subset V(\Gamma_i)\cap C\) then let \(c_k\) be a vertex of degree \(\leq n-r-2\) in the other component. Put \(y''(c_k)=2\). Now \(Q(\cH,y'')\) has no \((n-r)\)-bad component because both loops are in the same component. The only remaining possibility is that \(\lambda_1\) and \(\lambda_2\) are in different components of \(v^{\eps}\). It follows that \(\cH\) is Type 2.

If \(o(\cH)=n-r-2\), \(n-r\geq 6\) and \(Q(\cH,y)\) contains an \((n-r)\)-bad component then it contains exactly one, \(\Gamma\). If \(O(\cH)\subset C\backslash V(\Gamma)\) it follows that \(v^{\eps}\) is in a component \(\Gamma_2\) of \(Q(\cH,y')\) such that \(|V(\Gamma_2)\cap V|=|V(\Gamma_2)\cap C|\) with no slope and therefore \(\cH\) is Type 2. If \(O(\cH)\subset V(\Gamma)\) then observe that there is a component of \(Q(\cH,y')\) containing \(v^{\eps}\), \(c_k\) and every loop except one. The remaining loop is in a component with a vertex \(c_k'\) with degree \(\leq n-r-2\). Put \(y''(c_k')=2\). The every loop belongs to the same component of \(Q(\cH,y'')\) and therefore every component is \((n-r)\)-good.

If \(o(\cH)=n-r\) then \(y_1\) is the unique Ryser admissible complete loop-assignment for \(\cH\). Therefore \(\cH\) is embeddable if and only if every component of \(Q(\cH,y)\) is \((n-r)\)-good. If \(Q\) has an \((n-r)\)-bad component then \(\cH\) is Type 1.

Embedding symmetric latin squares \[sec5560\]

\[def5570\] A subset \(S\subseteq\Sigma\) is -bad if and only if (\[def55701\]), (\[def55702\]) and (\[def55703\]) hold.

1. \(\eps(S)=(k-2)/2\) \[def55701\]

2. \(r|S|-R(S)=k(|S|-j)\) \[def55702\]

3. \(|N(S)|=|S|-j\) \[def55703\]

\[def5580\] An externally off-diagonally prescribed symmetric latin square \(R\) of order \(n\) is Type 1 if and only if \(o(R)=n-r\) and either (\[def55801\]) or (\[def55802\]) holds.

1. \(\Sigma\) contains a \((2,n-r)\)-bad subset \(S\) and \(O(R)\subseteq S\) \[def55801\]

2. \(\Sigma\) contains a \((1,n-r)\)-bad subset \(S\) and \(O(R)\cap S=\emptyset\) \[def55802\]

\[def5590\] An externally off-diagonally prescribed symmetric latin square of order \(n\) is Type 2 if and only if \(o(R)=n-r-2\) and either (\[def55901\]) or (\[def55902\]) holds.

1. \(n-r=4\) and \(\Sigma\) contains \((j,n-r)\)-bad sets \(S\) and \(T\) such that \(O(R)\cap S=O(R)\cap T=\emptyset\) \[def55901\]

2. \(n-r\geq 6\) and \(\Sigma\) contains a \((1,n-r)\)-bad set \(S\) such that \(S\cap O(R)=\emptyset\) and a set \(T\) which satisfies (\[def559021\])-(\[def559024\])

   1. \(\eps(T)=0\) \[def559021\]

   2. \(r|T|-2e|T|=(|T|-1)(n-r)\) \[def559022\]

   3. \(|N(T)|=|T|-1\) \[def559023\]

   4. \(O(R)\subseteq T\) \[def559024\]

   \[def55902\]

\[thm5590\] An externally off-diagonally prescribed symmetric latin square \(L\) of order \(n\) on \(\Sigma\) can be embedded in some symmetric latin square of order \(n\) if and only if \(L\) is Ryser, admissible and not Type 1 nor Type 2.

This follows because \(L\) can be embedded in some symmetric latin square of order \(n\) if and only if the corresponding proper \(\Sigma\)-edge-coloured \(r\)-free-type simple graph \(\cH\) of order \(n\) can be embedded in a proper \(\Sigma\)-edge-coloured complete simple graph of order \(n\) and because, \(\cH\) is Ryser admissible if and only if \(L\) is Ryser admissible, \(\cH\) is Type 1 if and only if \(L\) is Type 1 and \(\cH\) is Type 2 if and only if \(L\) is Type 2