Chapter 5 Edge-coloured graphs

Introduction \[sec2000\] The aim of this chapter is to give necessary and sufficient conditions for embedding an \((n-1)\)-edge-coloured \(r\)-free-type simple graph of even order \(n\) in an \((n-1)\)-edge-coloured complete simple graph of order \(n\).

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

The necessity and insufficiency of being Ryser\[sec2010\] In this section the first aim is to give an explicit proof, in Lemma \[lem2020\], of the fact that a proper \(C_{[n-1]}\)-edge-coloured \(r\)-free-type simple graph of even order \(n\) which can be embedded in some proper \(C_{[n-1]}\)-edge-coloured complete simple graph of order \(n\) then is Ryser. In this chapter \(C=C_{[n-1]}\) throughout.

\[def2015\] A proper \(C\)-edge-coloured \(r\)-free-type simple graph \(\cH\) of order \(n\) is Ryser if and only if \(\ek\geq r-n/2+\Ek\) holds for all \(c_k\in C\).

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

Suppose \(\cK=(K,\Psi)\) is a proper \(C\)-edge-coloured complete simple graph of order \(n\) in which \(\cH\) is embedded. Then, by definition, there are \(\ek\) edges of colour \(c_{k}\) in \(\cK\) and, consequently, \(r-2\ek\) vertices in \(V(K)\cap V\) which are the end of no edge of colour \(c_{k}\) in \(\cK\). Moreover, among the free edges of \(H\) there are \(\Ek\) of colour \(c_{k}\) in \(\cK\). Therefore, as \(n-r\) vertices in \(V(K)\cap V(H)\) are the end of a free edge of \(H\), it follows that \(n-r-2\Ek\) vertices in \(V(K)\cap V(F(H))\) are the end of no edge of colour \(c_{k}\) in \(\cK\).

As \(d(K,u)=n-1\) for all \(u\in V(K)\), \(\cK\) is proper \(C\)-edge-coloured and \(|C|=n-1\) it follows that every vertex is the end of some edge of every colour \(c_k\in C\). Moreover, the only edges of colour \(c_{k}\in C\) with a vertex in \(V(K)\cap V\) as an end are either edges of \(E(K)\cap E(H^{\star})\) or edges sharing an end with a free edge of a colour other than \(c_{k}\). It follows that there must be at least as many vertices which are the ends of free edges of colours different from \(c_{k}\) as there are vertices in \(V(K)\cap V\) which are the end of no edge of colour \(c_{k}\). In other words, \((n-r)-2\Ek\geq r-2\ek\) holds and therefore \(\ek\geq r-n/2+\Ek\) also holds.

Example \[ex2030\] shows that, in general, being Ryser is insufficient for a proper \(C\)-edge-coloured \(r\)-free-type simple graph of order \(n\) to be embeddable in some proper \(C\)-edge-coloured complete simple graph of order \(n\).

\[ex2030\] The proper \(C_{[7]}\)-edge-coloured \(4\)-free-type simple graph \(\cH\) of order \(8\) in Figure \[fig2040\] is Ryser and yet cannot be embedded in a proper \(C_{[7]}\)-edge-coloured complete simple graph of order \(8\).

As \(r-n/2=0\) \(\cH\) is Ryser if and only if \(\ek\geq\Ek\) holds. If \(\Ek=0\), as is the case for \(c_{k}\in\{c_{3},\ldots,c_{7}\}\), then this condition is satisfied trivially. If, as for \(c_{k}\in\{c_{1},c_{2}\}\), we have \(\Ek=1\) then the condition is satisfied because in the edge-coloured \(K_{4}\) there is at least one edge of colour \(c_{k}\).

If \(vw\) is the free edge of colour \(c_2\) and \(\cH\) can be embedded in a proper \(C_{[7]}\)-edge-coloured complete simple graph \(\cK\) of order \(8\) then, in \(\cK\), vertices \(v\) and \(w\) are the ends of an edge \(e\neq vw\) of colour \(c_{1}\). This is a contradiction as every other vertex already is the end of an edge of colour \(c_{1}\).

Example \[ex2030\]

Not only is \(\cH\), in Figure \[fig2040\], not embeddable in every \(C_{[7]}\)-edge-coloured complete simple graph of order \(8\) but, as is shown in Example \[ex2085\], cannot even be embedded in a Ryser \(C_{[7]}\)-edge-coloured edge-extension of \(\cH\).

\[def2070\] If \(H\) is an \(r\)-free-type simple graph of order \(n\) and \(X\subseteq F\) then \(J=H\cdot X\) denotes the simple graph with vertex set \(V(J)=V(H)\) and edge-set \(E(J)=E(H)\cup\{vw\,|\,v\in V,w\mbox{ an end of some }\eps\in X\}\). If \(X=\{\eps\}\) then \(H\cdot\eps=H\cdot\{\eps\}\).

\[ex2072\] Figure \[fig2073\] shows a 3-free-type simple graph \(H\) of order 7 and \(H\cdot\eps\).

Example \[ex2072\]

\[lem2075\] If \(H\) is an \(r\)-free-type simple graph of order \(n\) and \(\eps\in F\) then \(H\cdot\eps\) is an \((r+2)\)-free-type simple graph of order \(n\).

Suppose \(H\) is an \(r\)-free-type simple graph of order \(n\). Then, by definition, \(H=H^{\star}\cup H_1\cup H_2\cup\ldots\cup H_{|F|}\), where \(H^{\star}\) is a complete simple graph of order \(r\) and \(H_1,H_2,\ldots, H_{|F|}\) are free-edges. Suppose, without loss of generality, that \(H_1=\eps\). Then \(H\cdot\eps = J^{\star}\cup H_2\cup H_2\cup\ldots\cup H_{|F|}\) where \(J^{\star}\) is a complete simple graph of order \(r+2\). Therefore as \(|V(J)|=|V(H)|=n\) and \(|V(J^{\star})|=|V(H^{\star})|+2=r+2\) it follows that \(H\cdot\eps\) is an \((r+2)\)-free-type simple graph of order \(n\).

\[def2080\] If \(\eps\in F(H)\) then a proper \(C\)-edge-coloured \(r\)-free-type simple graph \(\cH\) of order \(n\) is -extendible if and only if \(\cH\) can be embedded in a proper \(C\)-edge-coloured \((r+2)\)-free-type graph \(\cJ=(H\cdot\eps,(C,\psi))\).

The edge-coloured graph \(\cJ\) is an -extension of \(\cH\). An extension of \(\cH\) is a pair \((\eps,\cJ)\) where \(\eps\in F\) and \(\cJ\) is an \(\eps\)-extension of \(\cH\).

\[ex2085\] Suppose \(\cH\) is the proper \(C_{[7]}\)-edge-coloured \(4\)-free-type simple graph of order \(8\) in Figure \[fig2040\]. Let \(\eps\in F\) be the unique free-edge of colour \(c_2\) and suppose \(\cJ\) is an \(\eps\)-extension of \(\cH\). As \(c_{1}\) appears on two edges in \(E(H^{\star})\) it follows that, in \(\cJ\), there is no edge \(vw\), of colour \(c_{1}\), with \(v\in V\) and \(w\) an end of \(\eps\). Therefore \(\erkk=2\) and \(\Erkk=1\). As \(\erkk=2<3=(r+2)-n/2+\Erkk\) it follows by definition that \(\cJ\) is not Ryser.

In general, if \(\cH\) can be embedded in a proper \(C\)-edge-coloured complete simple graph \(\cK\) of order \(n\) and \(\eps\in F\), then it can be shown that the restriction of \(\cK\) to an \(\eps\)-extension \(\cJ\) of \(\cH\) is a Ryser \(\eps\)-extension of \(\cH\). From this observation it follows that \(\cH\) is completable only if \(\cH\) has a Ryser \(\eps\)-extension for every free-edge \(\eps\in F\).

\[def2086\] If \(\cH\) is a proper \(C\)-edge-coloured \(r\)-free-type simple graph of order \(n\) which is embedded in a proper \(C\)-edge-coloured complete simple graph \(\cK=(K,(C,\theta))\) of order \(n\), \(X\subseteq F\) and \(J=H\cdot X\) then the restriction \(\cK|_J\) is the edge-coloured graph \(\cJ=(J,(C,\psi))\) where \(\psi:E(J)\rightarrow C\) is defined by \(\psi(e)=\theta(e)\) for all \(e\in E(J)\).

A consequence of this definition, proved in Lemma \[lem2070\], is that if a proper \(C\)-edge-coloured \(r\)-free-type simple graph \(\cH\) of order \(n\) is embedded in a proper \(C\)-edge-coloured complete simple graph of order \(n\) and \(\eps\in F(H)\) then the restriction \(\cK|_{H\cdot\eps}\) is a Ryser proper \(\eps\)-extension of \(\cH\).

\[def2060\] If \(\cH\) is a proper \(C\)-edge-coloured \(r\)-free-type simple graph of order \(n\) then \(\cH\) is fully Ryser extendible if and only if \(\cH\) has a Ryser \(\eps\)-extension for every \(\eps\in F\).

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

Suppose \(\cK\) is a proper \(C\)-edge-coloured complete simple graph of order \(n\) in which \(\cH\) is embedded. If \(\eps\in F\) and \(J=H\cdot\eps\) then, as \(\cK\) is proper \(C\)-edge-coloured, it follows, from Lemma \[lem2075\], that \(\cJ=\cK|_J\) is a proper \(C\)-edge-coloured \((r+2)\)-free-type simple graph of order \(n\). Moreover, \(\cJ\) is embedded in \(\cK\) and \(\cK\) is a proper \(C\)-edge-coloured complete simple graph of order \(n\). Therefore, by Lemma \[lem2020\], \(\cJ\) is Ryser. Hence \(\cJ\) is a Ryser \(\eps\)-extension of \(\cH\). Therefore, \(\cH\) is fully Ryser extendible.

The proper \(C_{[7]}\)-edge-coloured \(4\)-free-type simple graph of order \(8\) in Figure \[fig2040\] is an example of a Ryser proper \(C\)-edge-coloured \(r\)-free-type simple graph of order \(n\) which is not fully extendible. If this example is not a counterexample to the conjecture of Dugdale and Hilton mentioned in the introduction it must be an instance of an \((n,r)\)-bad Ryser proper \(C\)-edge-coloured \(r\)-free-type simple graph of order \(n\). Fortunately, this is the case. If \(S=\{c_{1}\}\) then \(\eps(S)=(n-r-2)/2=1\), \(r|S|-2e(S)=4|S|-4=4(|S|-1)=(n-r)(|S|-1)\) and \(|N(S)|=0=|S|-1\).

In the next section necessary and sufficient conditions are found for a Ryser proper \(C\)-edge-coloured \(r\)-free-type simple graph of order \(n\) to be fully Ryser extendible.

Ryser extensions \[sec2080\] It is not true in general, as Example \[ex2030\] in Section \[sec2010\] shows, that a Ryser proper \(C\)-edge-coloured \(r\)-free-type simple graph of order \(n\) is fully Ryser extendible. In Example \[ex2030\] the problem seems to be caused by a single colour class \(c=[\cH,c_{1}]\) which, by virtue of the fact that it contains an edge with \(u\) as an end for all \(u\in V(H)\backslash\{v,w\}\) (where \(\eps=vw\) is the free edge of colour \(c_2\)), prevents \(\cH\) from being Ryser \(\eps\)-extendible. A consequence of \(c\) having this property is that \(c_1\) satisfies the Ryser condition with equality. The converse, that every colour which satisfies the Ryser condition with equality causes the same problem, is false. Nevertheless, colours which satisfy the Ryser condition with equality do have a degree of criticality about them. If \(\cJ\) is a Ryser \(\eps\)-extension then it can be shown that those colours \(c_k\neq\phi(\eps)\) which satisfy the Ryser condition with equality appear on two edges \(v_iv\), \(v_jw\) (where \(\eps=vw\)). Moreover, those which satisfy the Ryser condition with an excess of just one appear on at least one such edge. An example will make this clear.

\[ex2090\] If \(\cH\) is the proper \(C_{[7]}\)-edge-coloured \(4\)-free-type graph of order 8 in Figure \[fig2095\] then \(\cH\) is Ryser because \(\ek\geq 0\) for all \(c_{k}\in\{c_{1},c_{3},c_{5},c_{6},c_{7}\}\) and \(\ek\geq 1\) for \(c_{k}\in\{c_{2},c_{4}\}\) Of these, \(c_2,c_4\) and \(c_7\) satisfy \(\ek=r-n/2+\Ek\) while \(c_1,c_3,c_5\), \(c_6\) satisfy \(\ek=r-n/2+\Ek+1\). Suppose now that \(\cH\) has a Ryser \(\eps\)-extension \(\cJ\), where \(\eps\) is the unique free edge of colour \(c_2\). Then, because \(\cJ\) is Ryser, \(e(\cJ,c_k)\geq (r+2)-n/2+\eps(\cJ,c_k)\). If \(c_k\neq\phi(\eps)\) then \(\eps(\cJ,c_k)\neq\eps(c_k)\) and so \(e(\cJ,c_k)\geq\ek+2\). Therefore, if \(c_k\in\{c_4,c_7\}\), it follows that \(e(\cJ,c_k)\geq\ek+2\) and if \(c_k\in\{c_1,c_3,c_5,c_6\}\) then \(e(\cJ,c_k)\geq\ek+1\).

Example \[ex2090\]

In Example \[ex2090\] colours \(c_4\) and \(c_7\) are examples of critical colours, while \(c_1,c_3,c_5\) and \(c_6\) are all semi-critical. Critical and semi-critical colours \(c_k\) are identified by the value of \(\ek-(r-n/2+\Ek)\), so this quantity is given a special name in Definition \[def2100\].

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

Lemma \[lem2105\] follows immediately from the definition of Ryser.

\[lem2105\] A proper \(C\)-edge-coloured \(r\)-free-type simple graph of order \(n\) is Ryser if and only if \(\xk\geq 0\) for all \(c_k\in C\).

\[def2110\] A colour \(c_k\in C\) is critical if and only if \(\xk=0\) and semi-critical if and only if \(\xk=1\). If \(\xk\geq 2\) then \(c_k\) is stable

In Lemma \[lem2180\] below it is shown that an \(\eps\)-extension \(\cJ\) of \(\cH\) is Ryser if and only if \(E(J)\backslash E(H)\) contains two edges of colour \(c_k\) for every critical colour \(c_k\in C\backslash\{\phi(\eps)\}\) and at least one edge of colour \(c_k\) for every semi-critical colour \(c_k\in C\backslash\{\phi(\eps)\}\).

Now, fairly obviously, it is not true that a Ryser edge-extension can be constructed simply by finding two sets of colours with the property that every critical colour appears in both sets and every semi-critical colour appears in at least one. This is because an extension, by definition, is proper and, consequently, there are restrictions on which colours appear on edges in \(E(J)\backslash E(H)\). To be more precise, if \(vw\) is an edge with \(v\in V\) and \(w\) an end of \(\eps\) then the colour of the edge \(vw\) is used in \(\cH\) on no edge which has either \(v\) or \(w\) for an end.

\[def2120\] If \(\cH\) is a \(C\)-edge-coloured graph then \[C(v)=C(\cH,v)=\{c_k\in C\,|\,\mbox{an edge of colour }c_k\mbox{ in }\cH\mbox{ has }v\mbox{ as an end }\}\] \[M(v)=M(\cH,v)=C\backslash C(v)\] A colour \(c_k\in C\) is used in at if and only if \(c_k\in C(v)\) and missing in at if and only if \(c_k\in M(v)\).

If \(\cJ\) is a Ryser extension and \(S\subseteq C\) is the set of colours used in \(\cJ\) on the edges of \(E(J)\backslash E(H)\), then the maps \(\theta_v,\theta_w:V\rightarrow S\) defined by \(\theta_v(v_i)=c_k\) if and only if \(\psi(v_iv)=c_k\) and \(\theta_w(v_i)=c_k\) if and only of \(\psi(v_iw)=c_k\) have the property that both \(\theta_v(v_i)\in M(v)\) and \(\theta_w(v_i)\in M(v)\).

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

For an \(\eps\)-extension two pairs \((S,\theta_S)\) and \((T,\theta_T)\) are needed. \(S\) and \(T\) are both sets of \(r\) colours from \(C\) neither of which contain the colour \(\phi(\eps)\), \(\theta_S\) is an \(S\)-suitable map and \(\theta_T\) is a \(T\)-suitable map.

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

If \(\eps\in F\) then a \(\phi(\eps)\)-suitable pair is designed to correspond both to the set \(S\) of colours on edges of the form \(vw\) for \(v_i\in V\) and \(w\) an end of \(\eps\) and also to the map \(\theta:V\rightarrow S\) defined by \(\theta(v)=c_k\) if and only if \(\psi(vw)=c_k\). Now, because \(\eps\) has two ends, a pair of such pairs is needed. Moreover, there must be a degree of compatability between these two pairs in order to avoid two edges of the form \(v_iv\) and \(v_iw\), where \(\eps=vw\), being given the same colour.

\[def2160\] If \(\eps\in F\) and \(c_k\in C\) then a pair \(\{(S,\theta_S),(T,\theta_T)\}\) is -proper if and only if \((S,\theta_S)\) and \((T,\theta_T)\) are both \(c_k\)-suitable pairs and \(\theta_s(v)\neq\theta_t(v)\) holds for all \(v\in V\).

There is an obvious correspondence between \(\phi(\eps)\)-proper pairs and proper \(\eps\)-extensions.

\[def2164\] If \(\eps=vw\in F\) and \(\{(S,\theta_S),(T,\theta_T)\}\) is a \(\phi(\eps)\)-proper pair then the corresponding -extension is the edge-coloured graph \(\cJ=(J,(C,\psi))\) where \(J=H\cdot\eps\) and \(\psi\) is defined by \[\psi(e)=\left\lbrace\begin{array}{lll} \phi(e) & \mbox{iff} & e\in E(J)\cap E(H)\\ \theta_S(v_i) & \mbox{iff} & e=v_iv\mbox{ for some }v_i\in V \\ \theta_T(v_i) & \mbox{iff} & e=v_iw\mbox{ for some }v_i\in V \end{array} \right.\]

This correspondence is mutual.

\[def2166\] If \(\eps=vw\in F\) and \(\cJ=(J,(C,\psi))\) is a proper \(\eps\)-extension of \(\cH\) then the corresponding pair is the pair \(\{(S,\theta_S),(T,\theta_T)\}\) where \[S=\{c_k\in C\,|\, \psi(v_iv)=c_k\mbox{ for some }v_i\in V\}\] \[T=\{c_k\in C\,|\, \psi(v_iw)=c_k\mbox{ for some }v_i\in V\}\] and \(\theta_S:V\rightarrow S\), \(\theta_T:V\rightarrow T\) are defined by \(\theta_S(v_i)=\psi(v_iv)\) for all \(v_i\in V\) and \(\theta_T(v_i)=\psi(v_iw)\) for all \(v_i\in V\).

In Lemma \[lem2180\] it is shown that the \(\eps\)-extension corresponding to an \(\phi(\eps)\)-proper pair is a proper \(\eps\)-extension and the pair corresponding to an \(\eps\)-extension is a \(\phi(\eps)\)-proper pair.

\[lem2180\] If \(\eps\in F\) and \(\{(S,\theta_S),(T,\theta_T)\}\) is a \(\phi(\eps)\)-proper pair then the corresponding \(\eps\)-extension is a proper \(\eps\)-extension of \(\cH\). Conversely if \(\cJ\) is a proper \(\eps\)-extension then the corresponding pair is \(\phi(\eps)\)-proper.

First suppose \(\eps\in F\) and \(\{(S,\theta_S),(T,\theta_T)\}\) is a \(\phi(\eps)\)-proper pair. If \(\cJ=(J,(C,\psi))\) is the corresponding \(\eps\)-extension of \(\cH\) then, by definition, \(J=H\cdot\eps\). Therefore \(\cJ\) is a proper \(\eps\)-extension if and only \(\cJ\) is proper \(C\)-edge-coloured. As \(\phi(e)\in C\) and \(\theta_S(v_i)\in C\), \(\theta_T(v_i)\in C\) for all \(v_i\in V\) it follows that \(\cJ\) is \(C\)-edge-coloured. Therefore \(\cJ\) is proper \(C\)-edge-coloured if and only if \(\cJ\) is proper.

Let \(e\in E(J)\) and \(e'\in E(J)\) (\(e\neq e'\)) be edges with a common end. If \(\{e,e'\}\subseteq E(J)\cap E(H)\) then, by definition, \(\psi(e)=\phi(e)\neq\phi(e')=\psi(e')\). If \(\{e,e'\}\subseteq E(J)\backslash E(H)\) then, as \(e\) and \(e'\) have common end, it follows that either \(e=v_iv\) and \(e=v_iw\) for some \(v_i\in V(J)\cap V\) where \(\eps=vw\) or, without loss of generality, \(e=v_iv\) for some \(v_i\in V(J)\cap V\) and \(e'=\eps\). In the first case \(\psi(e)=\theta_S(v_i)\neq\theta_T(v_i)=\psi(e')\) while in the latter case as \(\psi(e')=\phi(\eps)\notin S\) and \(\psi(e)=\theta_S(v_i)\in S\) it follows that \(\psi(e)\neq\psi(e')\). Therefore \(\cJ\) is proper and hence a proper \(\eps\)-extension of \(\cH\).

Now suppose that \(vw=\eps\in F\), that \(\cJ=(J,(C,\psi))\) is a proper \(\eps\)-extension of \(\cH\) and \(\{(S,\theta_S),(T,\theta_T)\}\) is the corresponding pair. Then, by definition, \(S=\{c_k\in C\,|\,\psi(v_iv)=c_k\mbox{ for some }v_i\in V\}\) and \(T=\{c_k\in C\,|\,\psi(v_iw)=c_k\mbox{ for some }v_i\in V\}\). Therefore \(|S|=|T|=|V|=r\). Also, because \(\psi(vw)=\phi(\eps)\) and \(\cJ\) is proper it follows that \(\phi(\eps)\notin S\) and \(\phi(\eps)\notin T\). Finally because \(\cJ\) is proper \(\theta_S(v_i)\in M(v_i)\) and \(\theta_T(v_i)\in M(v_i)\) for all \(v_i\in V\). Therefore \(\theta_S:V\rightarrow S\) is \(S\)-suitable and \(\theta_T:V\rightarrow T\) is \(T\)-suitable. Now it follows that \(\{(S,\theta_S),(T,\theta_T)\}\) is a \(\phi(\eps)\)-proper pair.

The \(\phi(\eps)\)-proper pairs which are most interest are those pairs whose corresponding extension is Ryser.

\[def2170\] A \(\phi(\eps)\)-proper pair is Ryser if and only if the corresponding \(\eps\)-extension of \(\cH\) is Ryser.

In Lemma \[lem2200\] necessary and sufficient condititions are given for a \(\phi(\eps)\)-proper pair to be Ryser. The statement of Lemma \[lem2200\] involves notation introduced now in Definition \[def2180\].

\[def2180\] If \(\cH\) is a proper \(C\)-edge-coloured \(r\)-free-type simple graph of order \(n\) and \(\cJ\), \(\eps\in F\) and \(\cJ\) is an \(\eps\)-extension of \(\cH\) then \(\edk=\erkk-\erk\) for all \(c_k\in C\) and let \(\Edk=\Erkk-\Erk\) for all \(c_k\in C\).

The proof of Lemma \[lem2200\] is made considerably less labourious by the use of Lemma \[lem2190\].

\[lem2190\] If \(\{(S,\theta_S),(T,\theta_T)\}\) is \(\phi(\eps)\)-proper and \(\cJ\) is the corresponding proper \(\eps\)-extension of \(\cH\) then, for all \(c_k\in C\backslash\{\phi(\eps)\}\), \(\edk\geq 1\) if and only \(c_k\in S\cup T\) and \(\edk=2\) if and only if \(c_k\in S\cap T\).

By definition \(\theta_S\) and \(\theta_T\) are surjective. Therefore \(c_k\in S\) if and only if \(\theta_S(v_i)=c_k\) for some \(v_i\in V\) and \(c_k\in T\) if and only if \(\theta_T(v_i)=c_k\) for some \(v_i\in V\). As \(\cJ=(J,(C,\psi))\) is the corresponding \(\eps\)-extension \(\theta_S(v_i)=c_k\) if and only if \(\psi(v_iv)=c_k\) and \(\theta_T(v_i)=c_k\) if and only if \(\psi(v_iv)=c_k\) for some \(v_i\in V\). Therefore \(c_k\in S\cup T\) if and only if either \(\psi(v_iv)=c_k\) or \(\psi(v_iw)=c_k\) for some \(v_i\in V\) and \(c_k\in S\cap T\) if and only if \(\psi(v_iv)=\psi(v_iw)=c_k\). Therefore \(c_k\in S\cup T\) if and only if \(\edk\geq 1\) and \(c_k\in S\cap T\) if and only if \(\edk\geq 2\). The result follows because \(\edk\leq 2\) for all \(c_k\in C\).

\[lem2200\] If \(\eps\in F\) and \(\{(S,\theta_S),(T,\theta_T)\}\) is a \(\phi(\eps)\)-proper pair then \(\{(S,\theta_S),(T,\theta_T)\}\) is Ryser if and only if \(c_k\in S\cap T\) for every critical colour \(c_k\in C\backslash\{\phi(\eps)\}\) and \(c_k\in S\cup T\) for every semi-critical colour \(c_k\in C\backslash\{\phi(\eps)\}\).

By definition \(\{(S,\theta_S),(T,\theta_T)\}\) is Ryser if and only if the corresponding \(\eps\)-extension \(\cJ\) of \(\cH\) is Ryser. Now \(\cJ\) is \(n\)-Ryser, by definition, if and only if (\[eqn2210\]) holds for every \(c_k\in C\). \[\label{eqn2210} \erkk=(r+2)-n/2+\Erkk.\]

By definition \(\edk=\erkk-\erk\), therefore (\[eqn2220\]) holds for all \(c_k\in C\) \[\label{eqn2220} \erkk=\erk+\edk=r-n/2+\Erk+\xrk+\edk\]

If \(c_k=\phi(\eps)\) then \(\Erk=\Erkk+1\) and \(\edk=1\) so (\[eqn2220\]) says \(\erkk=(r+2)-n/2+\Erkk+\xrk\), which as \(\xrk\geq 0\) says that \(c_k\) satisfies (\[eqn2210\]). If \(c_k\neq\phi(\eps)\) then \(\Erk=\Erkk\) so (\[eqn2220\]) says \[\label{eqn2225} \erkk=r-n/2+\Erkk+\xrk+\edk\] If \(\xrk\geq 2\) then, because \(\edk\geq 0\), this implies (\[eqn2210\]). If \(\xrk=1\) then (\[eqn2225\]) implies (\[eqn2210\]) if and only if \(\edk\geq 1\). By Lemma \[lem2200\] \(\edk\geq 1\) if and only if \(c_k\in S\cup T\). If \(\xrk=0\) then (\[eqn2225\]) implies (\[eqn2210\]) if and only if \(\edk\geq 2\). As \(\edk\leq 2\) for all \(c_k\in C\) it follows from Lemma \[lem2200\] that \(\edk\geq 2\) if and only if \(c_k\in S\cap T\).

\[ex2230\] The proper \(C_{[7]}\)-edge-coloured \(6\)-free-type simple graph of order \(8\) in Figure \[fig2240\] is a Ryser \(\eps\)-extension of the proper \(C_{[7]}\)-edge-coloured \(4\)-free-type simple graph of order \(8\) in Figure \[fig2095\], where \(\eps=v_5v_6\). Here the Ryser \(\phi(\eps)\)-proper pair is \(\{(S,\theta_s),(T,\theta_t)\}\) where \(S=\{c_1,c_4,c_6,c_7\}\), \(T=\{c_3,c_4,c_5,c_7\}\) and \(\theta_S\) and \(\theta_T\) are given by \[\theta_S(v_1)=c_1,\theta_S(v_2)=c_4,\theta_S(v_3)=c_7,\theta_S(v_4)=c_6\] \[\theta_T(v_1)=c_4,\theta_T(v_2)=c_7,\theta_T(v_3)=c_5,\theta_T(v_4)=c_3\]

A Ryser Extension

Example \[ex2030\] shows that, in general, it is not true that a Ryser proper \(C\)-edge-coloured \(r\)-free-type simple graph of order \(n\) is fully Ryser extendible. However, it was also proved in Lemma \[lem2180\] that if \(\cH\) can be embedded in a proper \(C\)-edge-coloured complete simple graph of order \(n\) then \(\cH\) is fully extendible. The aim of this section is to obtain necessary and sufficient conditions for \(\cH\) to be fully extendible. Now an obvious necessary condition is that there are enough edges in \(E(J)\backslash E(H)\) to accomodate every critical colour \(c_k\neq\phi(\eps)\) twice and every semi-critical colour \(c_k\neq\phi(\eps)\) at least once. Fortunately, it so happens that \(E(J)\backslash E(H)\) always has enough edges. Before this is proved, in Lemma \[lem2260\], some notation which is common to the rest of this chapter is introduced in Definition \[def2250\]

\[def2250\] If \(n\) is even and \(\cH\) is a Ryser proper \(C\)-edge-coloured \(r\)-free-type simple graph of order \(n\) then for \(n-r=2\), \(i=0\) and \(n-r\geq 4\), \(i\in [n-r]\) if \(S\subseteq C\) let \[\Wi=\Whi=\{c_{k}\in S\,|\,\xrk=i\}\]\[\Wiplus=\Whiplus=\cup_{i\in [n-r]}\Whi\]\[\wi=\whi=|\Whi|\]\[\wiplus=\whiplus=|\Whiplus|\]

In other words, \(\Wzero=\Whzero\) is the subset of \(S\) consisting of critical colours and, if \(n-r\geq 4\), then \(\Wone=\Whone\) is the subset consisting of all semi-critical colours, while \(\Wtwoplus=\Whtwoplus\) is the subset of stable colours.

It is proved in Lemma \[lem2260\] that, numerically at least, there is no obstruction to a Ryser extension. In other words there are always enough edges in \(E(J)\backslash E(H)\) to accomodate two edges of every critical colour and at least one edge of every semi-critical colour. Lemma \[lem2260\] is something of a diversion and is not applied elsewhere.

\[lem2260\] If \(\eps\in F\) and \(\cJ\) is an \(\eps\)-extension of \(\cH\) then \(|E(J)\backslash E(H)|\geq 2\wzero+\wone\) if \(\phi(\eps)\) is stable, \(|E(J)\backslash E(H)|\geq 2\wzero+\wone-1\) if \(\phi(\eps)\) is semi-critical and \(|E(J)\backslash E(H)|\geq 2\wzero+\wone-2\) is \(\phi(\eps)\) is critical.

If \(n-r=2\), then as \(\cH\) is Ryser it follows that every colour is critical. Therefore it suffices to show that \(2r\geq 2(\wzeroC-1)\). This is obvious because every colour is critical, so \(\wzeroC=n-1\), and, because \(r=n-2\), it follows that \(2r=2(\wzeroC-1)\).

If \(n-r\geq 4\) it suffices to show that \(2r\geq 2\wzeroC+\woneC\) because, if \(\phi(\eps)\) is critical or semi-critical then the condition is weaker. Now, in \(V\) there are \(r\) vertices each of which is the end of \(r-1\) edges, so \(M(v_i)=(n-1)-(r-1)=n-r\) for all \(v_i\in V\). As each critical colour is missing at precisely \(n-r\) such vertices and each semi-critical colour is missing at precisely \(n-r-2\) it follows that, \[r(n-r)\geq (n-r)\wzeroC+(n-r-2)\woneC,\] therefore \[\begin{aligned} 2r & \geq & 2\wzeroC+2(1-2/(n-r))\woneC \\ & = & 2\wzeroC+\woneC+\woneC(1-4/(n-r)).\end{aligned}\] As \(n-r\geq 4\) this gives \(2r\geq 2\wzeroC+\woneC\).

So the question of whether it is necessary to impose any further conditions to ensure that a Ryser proper \(C\)-edge-coloured \(r\)-free-type simple graph can be Ryser extended is moot from the purely numerical point of view. However, there are further restrictions. Lemma \[lem2260\] assumes that every colour can be used on an edge \(vw\) with \(v\in V\) and \(w\) an end of \(\eps\) but of course only those colours in \(M(v)\) are available.

\[def2270\] If \(\cH\) is a proper \(C\)-edge-coloured \(r\)-free-type simple graph of order \(n\) and \(c_k\in C\) then \[N(c_k)=N(\cH,c_k)=\{v\in V\,|\,c_k\in M(v)\}\]

Now, because each vertex \(v\in V\) is the end of only two edges which also have an end in common with \(\eps\) it seems that, if \(\cH\) can be embedded in a proper \(C\)-edge-coloured complete simple graph, then, rather than just \(2r\geq 2\whzero+\whone\), the, apparently much stronger, condition \[2|\Nh|\geq 2\wzero+\wone\] is satisfied by all \(S\subseteq C\).

There is a slight inaccuracy here. As \(S\) is \(\phi(\eps)\)-suitable it follows that \(\phi(\eps)\notin S\). Therefore \(\phi(\eps)\) is not used on any edge of the form \(vw\) with \(v\in V\) and \(w\) an end of \(\eps\). However \(\phi(\eps)\) may very well be critical or semi-critical.

\[def2273\] If \(\cH\) is a proper \(C\)-edge-coloured \(r\)-free-type simple graph of even order \(n\), \(n-r\geq 4\) and \(S\subseteq C\) then \[\et=\eta(\cH,\eps,S)= \left\{ \begin{array}{lll} 0\mbox{ if }\phi(\eps)\notin\Wzero\cup\Wone \\ 1\mbox{ if }\phi(\eps)\in\Wone \\ 2\mbox{ if }\phi(\eps)\in\Wzero \end{array} \right.\]

In Lemma \[lem2280\] it is shown that \(|N(\cH,S)|\geq |S|-\n\), where \(\n\) is given in Definition \[def2275\], is necessary for \(\cH\) to have a Ryser \(\eps\)-extension.

\[def2275\] If \(\cH\) is a Ryser proper \(C\)-edge-coloured \(r\)-free-type simple graph of even order \(n\) then \[\n=\nh=\whtwoplus+(\whone+\eta(\cH,\eps,S))/2\]

\[lem2280\] If \(\cH\) is a Ryser proper \(C\)-edge-coloured \(r\)-free-type simple graph of even order \(n\), \(\cH\) has a Ryser \(\eps\)-extension for some \(\eps\in F\) and \(S\subseteq C\) then \[|N(\cH,S)|\geq |S|-\nh\]

Let \(\cJ\) be a Ryser \(\eps\)-extension of \(\cH\) and let \(S\subseteq C\). Among the \(2r\) edges of the form \(vw\), with \(v\in V\) and \(w\) an end of \(\eps\), there are at least \(2\wzero+\wone-\et\) which are coloured with some colour \(c_k\in S\). All of these edges, moreover, have an end in \(\N=N(\cH,S)\) and, because each of these vertices is the end of at most two such edges, it follows that \[2|\N|\geq 2\wzero+\wone-\et.\] Now, as \(|S|=\wzero+\wone+\wtwoplus\), it follows that \(2\wzero+\wone=2|S|-\wone-2\wtwoplus\) which gives \[2|\N|\geq 2|S|-(\wone+2\wtwoplus+\et).\] Therefore, \[|\N|\geq |S|-(\wone/2+\wtwoplus+\et/2)=|S|-\nu(\eps,S).\]

It was shown in Lemma \[lem2070\] that if \(\cH\) can be embedded in a proper \(C\)-edge-coloured complete simple graph of order \(n\) then \(\cH\) is fully Ryser extendible. However, Lemma \[lem2280\] implies that if \(C\) contains a subset \(S\) with the property that \(\N<|S|-\n\) then \(\cH\) is not fully-extendible. If there exists an instance of a proper \(C\)-edge-coloured \(r\)-free-type simple graph of order \(n\) with such a subset then the condition of Lemma \[lem2280\] is a new irredundant necessary condition for \(\cH\) to be embeddable in some proper \(C\)-edge-coloured complete simple graph of order \(n\). Example \[ex2320\] is just such an instance.

\[ex2320\] If \(\cH\) is the edge-coloured graph of Figure \[fig2040\], \(\eps\) is the free edge of colour \(c_2\) and \(S=\{c_1\}\) then, as \(c_1\) is semi-critical, it follows that \(\wone=1\) and \(\wtwoplus=0\). Therefore, as \(c_2\notin S\), it follows that \(\et=0\). Hence \(|S|-\n=1-(1+0+0)/2=1/2>0=|\N|\).

\[def2290\] If \(\eps\in F\) then a set \(S\subset C\) is an -obstruction if and only if \(|\N|<|S|-\n\). An obstruction of \(\cH\) is a pair \((\eps,S)\) where \(\eps\in F\) is a free-edge and \(S\subseteq C\) is an \(\eps\)-obstruction. If \(\cH\) has an obstruction then \(\cH\) is obstructed, otherwise \(\cH\) is unobstructed.

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

If \(\cH\) can be embedded in a proper \(C\)-edge-coloured complete simple graph of order \(n\) then, by Lemma \[lem2070\], \(\cH\) is fully-extendible. Therefore, if \(\eps\in F\), it follows by Lemma \[lem2280\] that \(|N(\cH,S)|\geq |S|-\nh\) for every subset \(S\subset C\). Therefore, by definition, \(\cH\) is unobstructed.

The question arises now as to whether the absence of obstructions is sufficient for a Ryser proper \(C\)-edge-coloured \(r\)-free-type simple graph of order \(n\) to be embeddable in some proper \(C\)-edge-coloured complete simple graph of order \(n\). In the first instance, because of Lemma \[lem2070\], the question of whether the absence of an obstruction even implies that \(\cH\) is fully Ryser extendible needs to be addressed. Eventually, in Section \[secXXXX\] this question is answered affirmatively. In the next section a very simple characterisation is given of obstructed \(n\)-Ryser proper \(C\)-edge-coloured \(r\)-free-type simple graphs of order \(n\). This characterisation is given in terms of the existence of a set of colours \(S\subseteq C\) with certain exact values for \(\wone\), \(\wtwoplus\) and \(\eps(S)\).

Obstructed Ryser edge-coloured free-type simple graphs \[sec2330\] An obstruction is, by definition, simply a subset \(S\subseteq C\) which satisfies a certain inequality. In this section we show that in fact this definition has a great deal of redundancy. The class of obstructed \(n\)-Ryser proper \(C\)-edge-coloured \(r\)-free-type simple graphs of order \(n\) actually seems to be very narrow. Apparently there are such tight restrictions on the parameters involved that only a single class of obstructed Ryser proper \(C\)-edge-coloured \(r\)-free-type simple graphs can squeeze through.

The approach of this section is simple. The aim is to show that for every \(\eps\in F\) an \(\eps\)-obstruction, in general, contains redundant colours. Redundant in this context means that an \(\eps\)-obstruction remains an \(\eps\)-obstruction after the removal of a redundant colour. After all redundant colours are removed the set which remains is an instance of a fundamental obstruction. The fundamental obstructions have the property that every obstructed \(n\)-Ryser proper \(C\)-edge-coloured \(r\)-free-type simple graph of order \(n\) has a fundamental \(\eps\)-obstruction for some \(\eps\in F\). So a characterisation of Ryser proper \(C\)-edge-coloured free-type simple graphs having a fundamental obstruction is a characterisation of all obstructed Ryser proper \(C\)-edge-coloured free-type simple graphs.

In this section a tool essential for the rest of this chapter is introduced. This tool is a certain multigraph \(\BH\) associated with a proper \(C\)-edge-coloured free-type simple graph \(\cH\). The multigraph \(\BH\) encodes all the essential information about \(\cH\), which colours are missing at which vertices of \(V\), which colours are on free edges and which colours are critical or semi-critica,l at the cost of encoding the precise structure of the edge-coloured graph \(\cH\).

The first application of this graph is to show that if \(\cH\) has a fundamental obstruction then it has an obstruction \((\eps,S)\) which satisfies \(\eps(S)=(n-r-2)/2\), \(\wone=1\) and \(\N=|S|-1\). This gives a precise characterisation of obstructed Ryser proper \(C\)-edge-coloured \(r\)-free-type simple graphs of order \(n\).

Recall that, by definition, an \(\eps\)-obstruction is a set \(S\subseteq C\) with the property that \(\N<|S|-\n\) for some \(\eps\in F\). Suppose now that \(\cH\) is a Ryser proper \(C\)-edge-coloured \(r\)-free-type simple graph of order \(n\) and that \(C\) contains an \(\eps\)-obstruction \(S\) with the property that \(\phi(\eps)\in S\). It is not difficult to see, and it is shown in the proof of Lemma \[lem2350\], that the set \(T=S\backslash\{\phi(\eps)\}\) is also an \(\eps\)-obstruction. Indeed, as \(\tN=\tNh\subset\N\) it follows that \(|\tN|\leq |\N|\) and so \(T\) is an \(\eps\)-obstruction if \(|T|-\tn\geq |S|-\nu(\eps,S)\), which, as \(|S|=|T|+1\), follows if \(\tn\leq\n-1\). This is proved in Lemma \[lem2350\] but, informally, it can be seen from the expression for \(\nu\) that if \(\phi(\eps)\) is stable then \(\nu\) drops by one because \(\wone\) and \(\eta\) are unchanged. If \(\phi(\eps)\) is critical or semi-critical then again \(\nu\) drops by one because \(\wtwoplus\) is unchanged but \(\wone+\eta(\eps,S)\) drops by two.

Now suppose \(\cH\) is Ryser and has an obstruction \((\eps,S)\) with \(\phi(\eps)\notin S\) and \(\wtwoplus>0\). In this case \(\n=\wtwoplus+\wone/2\) and this time it is easy to see that if \(c_k\in\wtwoplus\) then \(T=S\backslash\{c_k\}\) is also an \(\eps\)-obstruction because \(\wtwoplus\) drops by one and therefore \(\tn\leq\n-1\) holds.

These observations are summarised and proved in Lemma \[lem2350\].

\[def2340\] An obstruction \((\eps,S)\) is fundamental if and only if \(\phi(\eps)\notin S\) and \(\wtwoplus=0\).

\[lem2350\] If a Ryser proper \(C\)-edge-coloured \(r\)-free-type simple graph \(\cH\) of even order \(n\) has no fundamental obstruction then \(\cH\) is unobstructed.

Observe that if \(c_k\in S\) and \(T=S\backslash\{c_k\}\) satisfies \(\tn\leq\n-1\) then \(T\) is an \(\eps\)-obstruction if \(S\) is an \(\eps\)-obstruction. Indeed, as \(\tN\subset\N\), it follows that \(|\tN|\leq|\N|\) and so, if \(S\) is an \(\eps\)-obstruction, it follows that \(|\tN|<|S|-\n\leq (|T|+1)-(\nu(\eps,T)+1)= |T|-\tn\). Therefore \(T\) is also an \(\eps\)-obstruction.

If \(\phi(\eps)\in S\) then let \(T=S\backslash\{\phi(\eps)\}\). If \(\phi(\eps)\notin\Wzero\cup\Wone\) then \(\phi(\eps)\in\Wtwoplus\) and so it follows that \(\twtwoplus=\wtwoplus-1\), \(\twone=\wone\) and \(\tet=\et=0\). Therefore \(\tn=\n-1\). If \(\phi(\eps)\in\Wone\) then \(\twtwoplus=\wtwoplus\), \(\twone=\wone-1\) and \(\tet=\et-1\) and so, again, \(\tn=\n-1\). Finally, if \(\phi(\eps)\in\Wone\) then \(\twtwoplus=\wtwoplus\), \(\twone=\wone\) and \(\tet=\et-2\) and so, once again, \(\tn=\n-1\). In every case it follows from the conclusion of the opening paragraph that \(T\) is an \(\eps\)-obstruction.

Now suppose \(T\) is an \(\eps\)-obstruction with \(\phi(\eps)\notin S\) and \(\wtwoplus>0\). Let \(c_k\in\Wtwoplus\) and \(T=S\backslash\{c_k\}\). As \(\phi(\eps)\notin S\) it follows that \(\twone=\wone\) and \(\twtwoplus=\wtwoplus-1\). Therefore \(\tn=\n-1\) and so the conclusion of the opening paragraph again implies that \(T\) is an \(\eps\)-obstruction. If \(T\) satisfies \(\twtwoplus>0\) then apply the same procedure repeatedly to eventually end up with an \(\eps\)-obstruction \(U=S\backslash\Wtwoplus\) with \(\wtwoplus=0\).

Already Lemma \[lem2350\] has narrowed the seemingly broad class of obstructed Ryser proper \(C\)-edge-coloured \(r\)-free-type simple graphs of even order \(n\). It says that all such \(\cH\) have a fundamental obstruction. By definition a fundamental obstruction \((\eps,S)\) is an \(\eps\)-obstruction with the property that \(S\) contains neither any stable colour nor \(\phi(\eps)\) and also satisfies \(|\N|<|S|-\wone/2\).

Is it possible to be even more precise? For instance, is it possible for a fundamental \(\eps\)-obstruction to contain any number of semi-critical colours? Can \(S\) contain free-edge colours \(\phi(\eps')\neq\phi(\eps)\). Must \(S\) contain semi-critical colours or other free-edge colours? How about \(\N\)? Can a fundamental obstruction have \(\N=|S|-k\) for any \(k\geq 1\)? The answer to all these questions, given in Lemma \[lem2440\], is that every fundamental \(\eps\)-obstruction \((\eps,S)\) satisfies \(\wone=1\) and \(\N=|S|-1\) and, consequently, \(S\) contains every free-edge colour \(\phi(\eps')\neq\phi(\eps)\).

\[def2360\] A set \(S\subset C\) is -bad if and only if \(\wone=1\), \(\N=|S|-1\) and \(\eps(S)=(n-r-2)/2\). A Ryser proper \(C\)-edge-coloured \(r\)-free-type simple graph \(\cH\) of even order \(n\) is -bad if and only if \(n-r\geq 4\) and \(C\) contains an \((n-r)\)-bad set. Otherwise \(\cH\) is -good.

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

If \(\cH\) is not \((n-r)\)-good then \(\cH\) is \((n-r)\)-bad. If \(\cH\) is \((n-r)\)-bad then \(\cH\) is obstructed. Therefore, by Lemma \[lem2300\] \(\cH\) cannot be embedded in a proper \(C\)-edge-coloured complete simple graph of order \(n\).

It is proved in Lemma \[lem2440\] that if \(\cH\) is an \((n-r)\)-good Ryser proper \(C\)-edge-coloured \(r\)-free-type simple graph of even order \(n\) then \(\cH\) is unobstructed. The easiest proof of this fact involves a certain multigraph \(\BH\). This multigraph is one of the essential tools used in the rest of this chapter. The use of graphs like \(\BH\) in problems of this type is standard and, as shown in the introduction, has proved successful in the past.

\[def2370\] If \(\cH\) is a proper \(C\)-edge-coloured \(r\)-free-type simple graph of order \(n\) then \(B=\BH\) is the multigraph with vertex-set \(V(B)=V\cup C\) and edge-set \[E(B)=\{(v_ic_k,1)\,|\,v_i\in V,\,c_k\in M(v_i)\}\cup\{(c_kc_k,\eps(c_k))\,|\, c_k\in C\}\]

\[ex2380\] If \(\cH\) is the edge-coloured graph in Figure \[fig2095\] then \(\BH\) is the (multi)graph in Figure \[fig2390\]

\(\BH\) for \(\cH\) of Figure \[fig2095\]

Figure \[fig2390\] suggests that, in general, \(B=\BH\) has at least two distinctive properties. The most striking property is that \(d(B,v_i)=n-r\) for all \(v_i\in V(B)\cap V\). The reason for this is obvious. The degree of \(v_i\) in \(\BH\) is simply the number of colours missing at \(v_i\) in \(\cH\) and this is \((n-1)-(r-1)=n-r\). Of course this property is true of \(\BH\) in general. The other immediate property is that \(d(B,c_k)\) appears to be bounded above by \(n-r\). It is tempting to think that this property is true of \(\BH\) in general. Example \[ex2400\] dispels this misapprehension.

\[ex2400\] If \(\cH\) is the \(C_{[7]}\)-edge-coloured \(4\)-free-type simple graph of order \(8\) in Figure \[fig2410\] then \(B=\BH\) is the graph in Figure \[fig2420\]. Observe that \(d(B,c_2)=6>n-r=4\).

\(\cH\) of Ex \[ex2400\]

\(\BH\) for \(\cH\) in Fig \[fig2410\]

Of course the \(C_[7]\)-edge-coloured 4-free-type simple graph in Figure \[fig2410\] is an instance of a non-Ryser \(\cH\) because \(e(c_2)=0<r-n/2+\Ek=1\). Looking at \(\BH\) vertex \(c_2\) is the only vertex with degree greater than \(n-r\). This suggests that the degree bound on \(C\) is a reflection of \(\cH\) being Ryser. In Lemma \[lem2430\] it is shown that this hypothesis is correct.

\[lem2430\] If \(\cH\) is a proper \(C\)-edge-coloured \(r\)-free-type simple graph of even 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)=r-2\ek+2\Ek=(n-r)-2\xk\) for all \(c_k\in V(B)\cap C\).

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

Vertex \(c_k\in V(B)\cap C\) is the end of an edge \(v_ic_k\) for every vertex \(v_i\in V\) except those \(2\ek\) vertices which, in \(\cH\), are the end of an edge of colour \(c_k\). Furthermore, vertex \(c_k\) is the end of \(\Ek\) loops of \(B\). Therefore, \(d(B,c_k)=r-2\ek+2\Ek\). As \(\xk=\ek-(r-n/2+\Ek)\), by definition, it follows that \(d(B,c_k)=(n-r)-2\xk\) for all \(c_k\in V(B)\cap C\).

Now Lemma \[lem2105\] implies the following corollary.

\[cor2435\] If \(\cH\) is a proper \(C\)-edge-coloured \(r\)-free-type simple graph of even order \(n\) then \(\cH\) is Ryser if and only if \(\Delta(\BH)=n-r\).

The first application of \(\BH\) is to show, now, in Lemma \[lem2440\], that if \(\cH\) is Ryser and \((n-r)\)-good then \(\cH\) is not obstructed.

\[lem2440\] If \(\cH\) is an \((n-r)\)-good Ryser proper \(C\)-edge-coloured \(r\)-free-type simple graph of even order \(n\) then \(\cH\) is unobstructed.

The converse statement, that if \(\cH\) is an obstructed Ryser proper \(C\)-edge-coloured \(r\)-free-type simple graph of even order \(n\) then \(\cH\) is \((n-r)\)-bad, is proved.

Suppose that \(\cH\) is an obstructed Ryser proper \(C\)-edge-coloured \(r\)-free-type simple graph of even order \(n\). Then, by Lemma \[lem2350\], \(\cH\) has a fundamental obstruction \((\eps,S)\). The first step in the proof is to obtain a certain inequality which is used to show that \(\cH\) is \((n-r)\)-bad. This inequality is obtained by comparing an obvious upper bound on the number \(x=|\{v_ic_k\,|\,c_k\in S\mbox{ and }v_i\in\N\}|\) with an equally obvious exact value for \(x\) in terms of \(\wone\) and \(\Eks\).

Firstly, as each vertex in \(v_i\in\N\) satisifes \(d(B,v_i)=n-r\) it follows that \(x\leq |\N|(n-r)\). Secondly, from Lemma \[lem2430\] and because, as \((\eps,S)\) is fundamental, \(\wtwoplus=0\), it follows that every vertex \(c_k\in S\) satisfies \(d(B,c_k)=n-r\) except for those \(c_k\in\Wone\), all of which satisfy \(d(B,c_k)=n-r-2\). Therefore, \(d(B,S)=|S|(n-r)-2\wone\). Now because every non-loop edge which has an end in \(S\) also, by the definition of \(\N\), has an end in \(\N\), it follows that \(x=|S|(n-r)-2\wone-2\eps(S)\).

Therefore \(|S|(n-r)-2\wone-2\Eks\leq|\N|(n-r)\) which gives \(\p(n-r)\leq 2\Eks+2\wone\), where \(\p=|S|-|\N|\). As \(\phi(\eps)\notin S\) it follows that (\[eqn2450\]) holds. \[\label{eqn2450} \p(n-r)\leq (n-r-2)+2\wone\]

Now, as \((\eps,S)\) is a fundamental obstruction it follows by definition that (\[eqn2460\]) holds. \[\label{eqn2460} |\N|<|S|-\wone/2\] Therefore \(\wone<2\p\) and, because \(\wone\geq 0\), it follows that \(\p>0\).

From (\[eqn2460\]), as \(\wone\) and \(\p\) are non-negative integers, (\[eqn2470\]) follows. \[\label{eqn2470} \wone\leq 2\p-1\] and so (\[eqn2450\]) implies \(\p(n-r-4)\leq n-r-4\). If \(n-r>4\) then this gives \(\p\leq 1\) which, as \(\p>0\), implies \(\p=1\). From (\[eqn2460\]) it follows that \(\wone\leq 2\p-1=1\). Therefore \(S\) is a fundamental \(\eps\)-obstruction with \(\p=\wone=1\) and so \(\cH\) is \((n-r)\)-bad. As \(n-r\) is even the only remaining, non-trivial, cases are \(n-r=2\) and \(n-r=4\).

If \(n-r=2\) then \(\rho(C)\leq n-r-1=1\) implies \(\p\leq 1\) and so, as \(\p>0\), it follows that \(\p=1\). Every colour is critical so \(\wone=0\). This contradicts (\[eqn2450\]) which says \(n-r\leq n-r-2+2\wone\).

If \(n-r=4\) then (\[eqn2450\]) says \(4\p\leq 2+2\wone\) and so, as \(\wone\leq 4\), it follows that \(\p\leq 2\). If \(\p=1\) then, from (\[eqn2460\]) it follows that \(\wone=1\) and again \(S\) implies \(\cH\) is \((n-r)\)-bad. If \(\p=2\) then (\[eqn2470\]) and (\[eqn2450\]) imply \(\wone=3\). In this case \(T=C\backslash S\) has \(\rho(T)=\rho(C)-\p=3-2=1\) and \(\twone=\omega_1(C)-\wone=4-3=1\). So, in this case, \(T\) implies \(\cH\) is \((n-r)\)-bad.

At this point is has been shown that a fully Ryser extendible Ryser proper \(C\)-edge-coloured \(r\)-free-type simple graph \(\cH\) of order \(n\) is unobstructed and that if \(\cH\) is obstructed then it is \((n-r)\)-bad. There is, however, little point in trying to prove the converse, that an \((n-r)\)-good Ryser proper \(C\)-edge-coloured \(r\)-free-type simple graph \(\cH\) of order \(n\) is fully extendible. For not only is it necessary that \(\cH\) to be fully Ryser extendible but \(\cH\) must be fully Ryser extendible in such a way that the extensions are mutually compatible. In this context mutually compatible means that two different extensions \(\cJ\) and \(\cJ'\) must use different colours on edges incident with the same vertex \(v\in V\). Once again an example makes things clearer.

\[ex2480\] Figure \[fig2490\] shows another Ryser extension of \(\cH\) in Figure \[fig2095\]. The Ryser extension shown in Figure \[fig2490\] and the Ryser extension shown in Figure \[fig2240\] are incompatible because both cannot be embedded in the same proper \(C\)-edge-coloured complete simple graph of order \(8\). This is obvious because, for example, \(v_3v_5\) and \(v_3v_8\) both have colour \(c_7\).

A Ryser extension

Theoretically, at least, it may be possible for an \((n-r)\)-good Ryser proper \(C\)-edge-coloured \(r\)-free-type simple graph of order \(n\) to be both fully Ryser extendible and not embeddable in some proper \(C\)-edge-coloured complete simple graph of order \(n\). Remarkably, however, it turns out that being Ryser and \((n-r)\)-good is sufficient not only for \(\cH\) to be fully Ryser extendible but also for this stronger compatible extendibility.

\[def2500\] If \(\cH\) is a proper \(C\)-edge-coloured \(r\)-free-type simple graph of order \(n\) and \(F=\{\eps_1,\eps_2,\ldots ,\eps_{(n-r)/2}\}\) then \(\cH\) is semi-completable if and only if \(\cH\) can be embedded in a proper \(C\)-edge-coloured graph \(\cK=(K,(C,\theta))\), where \(K=H\cdot\{\eps_1,\eps_2,\ldots,\eps_{(n-r)/2}\}\}\), such that, for every \(\eps_i\in F\), the edge-coloured graph \(\cJ_i=(J_i,(C,\psi_i))\) where \(J_i=H\cdot\eps_i\) and \(\psi_i:E(J_i)\rightarrow C\) is defined by \(\psi_i(e)=\theta(e)\) for all \(e\in E(J_i)\) is a Ryser \(\eps_i\)-extension of \(\cH\).

In general, if \(\cH\) is semi-completable and \(F=\{\eps_i\,|\,i\in [n-r]\}\) then it can be shown that \(\BH\) has a decomposition \(\cB=\{B_i\,|\,i\in [n-r]\}\) such that, for all \(i\in [n-r]\), the subgraph \(B_i\) corresponds to a Ryser \(\eps_i\)-proper pair. The edge disjoint property of the decomposition then corresponds to the corresponding extensions being mutually compatible. It might seem optimistic to expect that being Ryser and \((n-r)\)-good, conditions which were introduced only to ensure that \(\cH\) is fully extendible, are also sufficient for semi-completability. However, as shown in Section \[sec2510\], this happens to be the case.

Ryser proper subgraphs of \(\BH\) \[sec2510\] The aim of this section is to apply \(\BH\) to the problem of constructing Ryser \(\phi(\eps)\)-proper pairs. This is done by establishing a correspondence between Ryser \(\phi(\eps)\)-proper pairs and certain subgraphs of \(\BH\). This correspondence is built up in a similar way to the definition of an \(\phi(\eps)\)-proper pair. The first step in the process is to identify subgraphs of \(\BH\) which correspond to \(\phi(\eps)\)-suitable pairs.

\[def2520\] If \(c_k\in C\) then the graph corresponding to a -suitable pair \((S,\theta)\) is the graph \(A=A(S,\theta)\) where \(V(A)=V\cup C\) and \(E(A)=\{v_ic_k\,|\,v_i\in V, c_k\in S\mbox{ and }\theta(v_i)=c_k\}\).

\[lem2525\] The graph \(A\) corresponding to a \(c_k\)-suitable pair is a uniquely defined defined subgraph of \(\BH\).

The uniqueness follows because, trivially, \(V(A)=V\cup C\) is uniquely defined and because \(E(A)=\{v_ic_k\,|\,v_i\in V, c_k\in S\mbox{ and }\theta(v_i)=c_k\}\) is uniquely defined because \(\theta\) is well-defined. \(A\) is a subgraph of \(B=\BH\) because \(V(A)=V(B)\) and \(E(A)=\{v_ic_k\,|\,v_i\in V, c_k\in S\mbox{ and }\theta(v_i)=c_k\}\subseteq E(B)\).

\[ex2530\] If \(\cH\) is the \(8\)-Ryser proper \(\eps\)-extension \(\cJ\), shown in Figure \[fig2240\], of the proper \(C_{[7]}\)-edge-coloured \(4\)-free-type simple graph \(\cH\) of order \(8\) shown in Figure \[fig2095\] then the corresponding \(\phi(\eps)\)-proper pair is \(\{(S,\theta_S),(T,\theta_T)\}\) where \(S=\{c_1,c_4,c_6,c_7\}\), \(T=\{c_3,c_4,c_5,c_7\}\) and \(\theta_S\) and \(\theta_T\) are given by \[\theta_S(v_1)=c_1,\theta_S(v_2)=c_4,\theta_S(v_3)=c_7,\theta_S(v_4)=c_6\] \[\theta_T(v_1)=c_4,\theta_T(v_2)=c_7,\theta_T(v_3)=c_5,\theta_T(v_4)=c_3\] The graph \(A_S=A_S(S,\theta_S)\) corresponding to \((S,\theta_S)\) is shown on the left of Figure \[fig2540\] while the graph \(A_T=A_T(T,\theta_T)\) corresponding to \((T,\theta_T)\) is shown on the right.

Ex \[ex2530\]

The question now arises as to which subgraphs of \(\BH\) correspond to \(\phi(\eps)\)-suitable pairs.

\[def2550\] If \(c_k\in C\) then a graph \(A\) is a -suitable graph if and only if \(A\) is the graph corresponding to some \(c_k\)-suitable pair.

The graphs in Figure \[fig2540\] have some obvious properties. Every vertex \(v\in V\) is the end of some edge of \(A_S\) and some edge of \(A_T\), every vertex \(c_k\in S\) is the end of some edge of \(A_S\), every vertex of \(T\) is the end of some edge of \(A_T\) and \(\phi(\eps)=c_2\) is the end of no edge of either \(A_S\) or \(A_T\). In Lemma \[lem2560\] it is proved that, unsurprisingly, these properties are sufficient for a subgraph of \(\BH\) to be the corresponding graph of some \(c_t\)-suitable pair.

\[lem2560\] If \(\cH\) is a proper \(C\)-edge-coloured \(r\)-free-type simple graph of order \(n\), \(c_k\in C\) then \(A\) is \(c_k\)-suitable if and only if \(A\triangleleft\BH\) and (\[lem25601\]), (\[lem25602\]) and (\[lem25603\]) hold.

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

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

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

If \(A\triangleleft B\) is \(c_k\)-suitable then, by definition, there exists a \(c_k\)-proper pair \((S,\theta)\) for which \(A\) is the corresponding subgraph of \(B\). By definition \(E(A)=\{v_ic_j\,|\,v_i\in V,c_j\in S,\mbox{ and }\theta(v_i)=c_j\}\). Therefore as \(\theta:V\rightarrow S\) it follows that \(d(A,v_i)=1\) for all \(v_i\in V\). Moreover, as \(\theta\) is injective it follows that \(d(A,c_j)\leq 1\) for all \(c_j\in C\) and therefore \(\Delta(A)=1\). Finally, as \((S,\theta)\) is \(\phi(\eps)\)-suitable, it follows that \(\phi(\eps)\notin S\) and therefore \(d(A,\phi(\eps))=0\).

If \(A\triangleleft B\) satisfies (\[lem25601\])-(\[lem25603\]) let \(S=\{c_j\in C\,|\,d(A,c_j)=1\}\) and define \(\theta:V\rightarrow S\) by \(\theta(v_i)=c_j\) if and only if \(v_ic_j\in E(A)\). From (\[lem25601\]) it follows that \(A\) is loopless, therefore as \(A\triangleleft B\) it follows that \(A\) has bipartition \(\{V,S\}\). Now from (\[lem25601\]) and (\[lem25602\]) it follows that \(E(A)\) is an independent set of edges \(|V|=r\) edges. Therefore \(|S|=r\). By the definition of \(S\) it follows from (\[lem25603\]) that \(\phi(\eps)\notin S\) and therefore \((S,\theta)\) is \(\phi(\eps)\)-suitable if and only if \(\theta\) is \(S\)-suitable. If \(\theta(v_i)=\theta(v_I)\) then by (\[lem25601\]) it follows that \(i=I\) and hence \(\theta\) is injective. Finally, if \(\theta(v_i)=c_j\) then, by definition, \(v_ic_j\in E(A)\) and so \(v_ic_j\in E(B)\) which implies \(c_j\in M(v_i)\). Hence \(\theta\) is \(S\)-suitable and so \((S,\theta)\) is \(\phi(\eps)\)-suitable. Therefore as \(A\) is the subgraph of \(B\) corresponding to \((S,\theta)\) it follows, by definition, that \(A\) is \(\phi(\eps)\)-suitable.

It is clear, and proved in Lemma \[lem2580\], that a \(c_k\)-suitable graph corresponds uniquely to some \(c_k\)-suitable pair.

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

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

Suppose \((S,\theta)\) is the corresponding pair. By definition \(S\subseteq C\) and by Lemma \[lem2560\], as \(d(A,c_k)=0\) it follows from Lemma \[lem2710\] that \(c_k\notin S\). By (\[lem25602\]) \(|S|=r\), therefore, by (\[lem25601\]), \(\theta:V\rightarrow S\) is bijective and because \(\theta(v_i)=c_j\) if and only if \(v_ic_j\in E(A)\) it follows, by the definition of \(\BH\), that \(c_k\in M(v_i)\).

As the subgraph corresponding to a \(c_t\)-suitable pair is, by Lemma \[lem2525\], unique it follows that the correspondence between \(c_t\)-suitable pairs and \(c_t\)-suitable subgraphs is bijective. The idea now is to build on this correspondence to find a correspondence between \(\phi(\eps)\)-proper pairs and subgraphs of \(\BH\).

\[def2590\] If \(\eps\in F\) then the graph corresponding to a -proper pair \(\{(S,\theta_S),(T,\theta_T)\}\) is \(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),1)\}\).

\[ex2600\] The union of the two \(\phi(\eps)\)-suitable graphs of Figure \[fig2540\] and a graph consisting of vertex \(c_2\) and a loop with \(c_2\) as an end gives the corresponding \(\phi(\eps)\)-proper graph, shown in Figure \[fig2610\].

Ex \[ex2600\]

The obvious question to ask now is which subgraphs of \(\BH\) correspond to \(\phi(\eps)\)-proper pairs.

\[def2620\] If \(\eps\in F\) then a graph \(A\triangleleft B\) is -proper if and only if \(A\triangleleft\BH\) is the graph corresponding to some \(\phi(\eps)\)-proper pair.

\[lem2630\] If \(\eps\in F\) then \(A\triangleleft\BH\) is \(\phi(\eps)\)-proper if and only if (\[lem26301\])-(\[lem26304\]) hold.

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

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

3. \(|E(A)|=2r+1\) \[lem26303\]

4. \((\phi(\eps)\phi(\eps),1)\in E(A)\) \[lem26304\]

If \(A\triangleleft B=\BH\) is \(\phi(\eps)\)-proper then, by definition, there exists an \(\phi(\eps)\)-proper pair \(\{(S,\theta_S),(T,\theta_T)\}\) for which \(A\) is the corresponding graph. Therefore, by definition, \(A=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),1))\).

By Lemma \[lem2560\] it follows that \(d(A_S,\phi(\eps))=d(A_T,\phi(\eps))=0\). Therefore, as \(A=A_S\cup A_T\cup\{\lambda\}\), it follows that \(d(A,\phi(\eps))=d(A_S,\phi(\eps))+d(A_T,\phi(\eps))+2=2\) and \(d(A,u)=d(A_S,u)+d(A_T,u)\) for all \(u\in V(A)\backslash\{\phi(\eps)\}\). Consequently, \(\Delta(A)\leq\Delta(A_S)+\Delta(A_T)=2\). Now, as \(d(A,\phi(\eps))=2\) it follows that \(\Delta(A)=2\). Moreover, \(d(A,v)=d(A_S,v)+d(A_T,v)=2\) for all \(v\in V\). Finally, \(e\in E(A)\) if and only if \(e\in E(A_S)\), \(e\in E(A_T)\) or \(e=\lambda\). Therefore \(|E(A)|=|E(A_S)|+|E(A_T)|+1=2r+1\).

Now suppose \(A\triangleleft B\) satisfies (\[lem26301\])-(\[lem26304\]). As every non-loop edge of \(A\), being also an edge of \(B\), is of the form \(v_ic_k\) for some \(v_i\in V\) and \(c_k\in C\) and \(A\) has no loop with an end in \(V\) it follows from (\[lem26302\]) that \(E(A)\) contains exactly \(2r\) non-loop edges and therefore, from (\[lem26303\]), that \(E(A)\) contains exactly one loop, \(\lambda\) say. From (\[lem26304\]) it follows that \(\lambda=(\phi(\eps)\phi(\eps),1)\). Let \(X=(V(A),E(A)\backslash\lambda)\).

If \(X_1,X_2,\ldots,X_y\) are all the components of \(X\) with at least two vertices then by (\[lem26301\]) it follows that \(X_i\) is a path or cycle for all \(i\in [y]\). Moreover, by (\[lem26302\]), the length of \(X_i\) is even for all \(i\in [y]\). For all \(i\in [y]\), if \(X_i=(v_0,e_1,v_1,\ldots,v_{2m-1},e_{2m},v_{2m})\), where \(m=m(i)\), let \(E_{i,1}=\{e_1,e_3,\ldots,e_{2m-1}\}\) and \(E_{i,2}=\{e_2,e_4,\ldots,e_{2m}\}\). Then let \(A_S=(V(B),\cup_{i\in [y]}E_{i,1})\) and \(A_T=(V(B),\cup_{i\in [y]}E_{i,2})\).

If \(u\in V(X)\) satisfies \(d(X,u)=2\) then, as the two edges of \(X\) with \(u\) as an end are consecutive edges of some path or cycle component of \(X\) it follows that \(d(A_S,u)=d(A_T,u)=1\). If \(u\in V(X)\) satisfies \(d(X,u)=1\) then, as the unique edge of \(X\) with \(u\) as an end is either an edge of \(A_S\) or an edge of \(A_T\), but not of both, it follows that either \(d(A_S,u)=1\) and \(d(A_T,u)=0\) or \(d(A_T,u)=1\) and \(d(A_S,u)=0\). Finally, if \(u\in V(X)\) satisfies \(d(X,u)=0\) then, as \(d(A_S,u)\leq d(X,u)=0\) and \(d(A_T,u)\leq d(X,u)=0\) it follows that \(d(A_S,u)=d(A_T,u)=0\).

Therefore (\[lem26302\]) implies that \(d(A_S,u)=d(A_T,u)=1\) for all \(v\in V\) and consequently (\[lem26301\]) implies \(\Delta(A_S)=\Delta(A_T)=1\). Finally, by (\[lem26304\]) and (\[lem26301\]), it follows that \(d(A_S,\phi(\eps))=d(A_T,\phi(\eps))=0\). Therefore, by Lemma \[lem2560\] it follows that \(A_S\) and \(A_T\) are both \(\phi(\eps)\)-suitable. Therefore, as \(A=A_S\cup A_T\cup (\{\phi(\eps)\},(\phi(\eps)\phi(\eps),1))\) it follows that \(A\) is \(\phi(\eps)\)-proper.

Now, unlike the correspondence between \(\phi(\eps)\)-suitable subgraphs and \(\phi(\eps)\)-suitable pairs, the correspondence between \(\phi(\eps)\)-proper pairs and \(\phi(\eps)\)-proper subgraphs is not bijective. For a given \(\phi(\eps)\)-proper subgraph \(A\) there are, in general, many \(\phi(\eps)\)-proper pairs which have \(A\) as their corresponding subgraph.

\[ex2640\] Figure \[fig2650\] shows a decomposition of \(A\) of Figure \[fig2610\] into \(\phi(\eps)\)-suitable subgraphs. The corresponding \(\phi(\eps)\)-proper pair is obviously different from the \(\phi(\eps)\)-proper pair of Example \[ex2530\] and yet both have the graph of Figure \[fig2610\] as their corresponding graph.

An alternative decomposition

\[def2660\] If \(\eps\in F\) and \(A\) is a \(\phi(\eps)\)-proper graph then a decomposition \(\cA\) of \(A\) is suitable if and only if \(\cA=\{A_S,A_T,\lambda\}\), where \(A_S\) and \(A_T\) are both \(\phi(\eps)\)-suitable and \(\lambda=(\{\phi(\eps)\},(\phi(\eps)\phi(\eps),1))\).

\[def2670\] If \(\eps\in F\) then \((A,\cA)\) is a suitably decomposed -proper subgraph of if and only if \(A\) is a \(\phi(\eps)\)-proper graph and \(\cA=\{A_S,A_T,\lambda\}\) is a suitable decomposition of \(\cA\)

\[def2680\] The extension corresponding to a suitably decomposed -proper subgraph is the \(\eps\)-extension corresponding to \(\{(S,\theta_S),(T,\theta_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\) and \(\cA=\{A_S,A_T,\lambda\}\).

\[lem2690\] The \(\eps\)-extension corresponding to a suitably decomposed \(\phi(\eps)\)-proper graph is a uniquely defined proper \(\eps\)-extension of \(\cH\).

The extensions which are of most interest are the Ryser extensions. Inevitably the property of being Ryser imposes restrictions on the corresponding subgraphs of \(\BH\).

\[def2700\] If \(\eps\in F\) then a \(\phi(\eps)\)-proper graph \(A\) is Ryser if and only if, for every suitable decomposition \(\cA\) of \(A\), the \(\eps\)-extension corresponding to \((A,\cA)\) is Ryser.

Necessary and sufficient conditions for a \(\phi(\eps)\)-proper subgraph to be Ryser are given in Lemma \[lem2730\]. The proof of this result is made considerably less tedious by the two observations of Lemma \[lem2710\] and Lemma \[lem2720\], the latter of which is really a corollary of the former.

\[lem2710\] If \((S,\theta)\) and \(A\) are corresponding \(c_k\)-suitable pair and \(c_k\)-suitable graph then \(d(A,c_j)=1\) if and only if \(c_j\in S\), for all \(c_j\in C\).

By definition \(E(A)=\{v_ic_j\,|\,v_i\in V,c_j\in S,\theta(v_i)=c_j\}\). Therefore \(d(A,c_j)\geq 1\) if and only if \(c_j\in S\). Now, by Lemma \[lem2560\](\[lem25601\]) it follows that \(d(A,c_j)=1\) if and only if \(c_j\in S\).

\[lem2720\] If \(\{(S,\theta_S),(T,\theta_T)\}\) and \(A\) are corresponding \(\phi(\eps)\)-proper pair and \(\phi(\eps)\)-proper graph then, for all \(c_k\in C\backslash\{\phi(\eps)\}\), \(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\).

By definition \(A=A_S\cup A_T\cup\{\lambda\}\), where \(A_S\) is the graph corresponding to \((S,\theta_S)\), \(A_T\) is the graph corresponding to \((T,\theta_T)\) and \(\lambda=(\{\phi(\eps)\},(\phi(\eps)\phi(\eps),1))\). By Lemma \[lem2710\] \(d(A_S,c_k)=1\) if and only if \(c_k\in S\) and \(d(A_T,c_k)=1\) if and only if \(c_k\in T\). For all \(c_k\in C\backslash\{\phi(\eps)\}\) it follows as \(A=A_S\cup A_T\cup\{\lambda\}\) that \(d(A,c_k)=d(A_S,c_k)+d(A_T,c_k)\). Therefore \(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\).

\[lem2730\] If \(\eps\in F\) then an \(\phi(\eps)\)-proper graph \(A\) is Ryser if and only if (\[lem27301\]) and (\[lem27302\]) both hold.

1. \[lem27301\] If \(c_k\in C\) satisfies \(d(B,c_k)=n-r\) then \(d(A,c_k)=2\)

2. \[lem27302\] If \(c_k\in C\) satisfies \(d(B,c_k)=n-r-2\) then \(d(A,c_k)\geq 1\)

If \(A\) is Ryser then, by definition, there is a Ryser \(\phi(\eps)\)-proper pair \(\{(S,\theta_S),(T,\theta_T)\}\) for which \(A\) is the corresponding graph. If \(d(B,c_k)=n-r\) then by Lemma \[lem2430\] \(c_k\) is critical and so by Lemma \[lem2200\] \(c_k\in S\cap T\). It follows from Lemma \[lem2720\] that \(d(A,c_k)=2\). If \(d(B,c_k)=n-r-2\) then, by Lemma \[lem2430\], it follows that \(c_k\) is semi-critical and so, by Lemma \[lem2200\], \(c_k\in S\cup T\). Therefore by Lemma \[lem2720\] it follows that \(d(A,c_k)\geq 1\).

If \(A\) if \(\phi(\eps)\)-proper then, by definition, there exists a \(\phi(\eps)\)-proper pair \(\{(S,\theta_S),(T,\theta_T)\}\) for which \(A\) is the corresponding graph. If \(c_k\in C\backslash\{\phi(\eps)\}\) is critical then by Lemma \[lem2430\] it follows that \(d(B,c_k)=n-r\). Therefore by (\[lem27301\]) it follows that \(d(A,c_k)=2\) and so by Lemma \[lem2720\] it follows that \(c_k\in S\cap T\). If \(c_k\in C\backslash\{\phi(\eps)\}\) is semi-critical then by Lemma \[lem2430\] it follows that \(d(B,c_k)=n-r-2\). Therefore by (\[lem27302\]) it follows that \(d(A,c_k)\geq 1\) and so by Lemma \[lem2720\] it follows that \(c_k\in S\cup T\). By Lemma \[lem2200\], \(\{(S,\theta_S),(T,\theta_T)\}\) is Ryser and so, as \(A\) is the corresponding graph. \(A\) is, by definition, Ryser.

\[ex2740\] If \(\eps=v_5v_6\) and \(\cJ\) is the Ryser \(\eps\)-extension, shown in Figure \[fig2240\], of the proper \(C_{[7]}\)-edge-coloured \(4\)-free-type simple graph \(\cH\) of order \(8\) shown in Figure \[fig2095\] then the graph in Figure \[fig2610\], is a Ryser \(\phi(\eps)\)-proper graph.

Provisional extensions \[sec2750\]

An important feature of the proof of Theorem \[thm3270\] is the use of provisional extensions.

\[def2760\] An \(\eps\)-extension \(\cJ\) is provisional if and only if \(v_{r+1}\) and \(v_{r+2}\) belong to the same component of \(\BJ\).

\[ex2770\] The Ryser extension \(\cJ\) of Figure \[fig2240\] is provisional because \(\BJ\) is the graph in Figure \[fig2775\] and the highlighted path shows that \(v_5\) and \(v_6\) are vertices of the same component of \(\BJ\).

\(\BJ\) for \(\cJ\) in Figure \[fig2240\]

Provisional extensions are only of interest because the proof of Theorem \[thm3270\] depends on them, and even then the use of such extensions is really just a convenience. It seems likely that Theorem \[thm3270\] could be proved without the use of provisional extensions.

\[def2780\] If \(\cJ\) is a provisional extension then \(S=S(\cJ)\) denotes the component of \(B=\BJ\) containing \(v_{r+1}\) and \(v_{r+2}\) and \(T=T(\cJ)=(V(B)\backslash V(S),E(B)\backslash E(S))\).

Perhaps surprisingly it happens that every \(\phi(\eps)\)-proper graph is the corresponding graph of some provisional \(\eps\)-proper extension. In other words a Ryser \(\phi(\eps)\)-proper graph always has a provisional suitable decomposition.

\[def2790\] A suitable decomposition \(\cA\) of a \(\phi(\eps)\)-proper graph \(A\) is provisional if and only if the extension corresponding to \((\cA,A)\) is provisional.

\[lem2800\] If \(n-r\geq 4\) then every \(\phi(\eps)\)-proper graph has a provisional suitable decomposition.

Suppose that \(A\) is a \(\phi(\eps)\)-proper graph and \(\{(S,\theta_S,c_s),(T,\theta_T,c_t)\}\) is the corresponding \(\phi(\eps)\)-proper pair. If there exists some \(c_k\in V(A)\cap C\) such that \(d(A,c_k)=0\) then, by Lemma \[lem2720\], \(c_k\notin S\) and \(c_k\notin T\), therefore \(c_k\in M(\cJ,v_{r+1})\) and \(c_k\notin M(\cJ,v_{r+2})\). By the definition of \(B'=\BJ\) it follows that \(v_{r+1}c_k\in E(B')\) and \(v_{r+2}c_k\in E(B')\) and, consequently, \(v_{r+1}\) and \(v_{r+2}\) are vertices of the same component of \(B'\).

If \(d(A,c_k)>0\) for all \(c_k\in V(A)\cap C\) then, by Lemma \[lem2630\] (\[lem26301\]) it follows that \(d(A,c_k)\in\{1,2\}\) for all \(c_k\in V(A)\cap C\). If \(x=|X|\) where \(X=|\{c_k\in V(A)\cap C\,|\, d(A,c_k)=2\}|\) and \(y=|Y|\) where \(Y=|\{c_k\in V(A)\cap C\,|\, d(A,c_k)=1\}|\) then \(x+y=n-1\) and \(|E(A)|=2r+1=2x+y\). Therefore \(y=2(n-r-2)\) and, because \(n-r\geq 4\), there are at least \(4\) vertices \(c_k\in C\) which satisfy \(d(A,c_k)=1\).

Let \(B\backslash A=(V(B),E(B)\backslash E(A))\). If \(c_k\in Y\) then \(d(B\backslash A,c_k)\) is odd. Therefore the component \(\Gamma\) of \(B\backslash A\) containing \(c_k\) also contains \(c_K\) of odd degree and \(d(A,c_K)=1\).

Let \(\cA=(A_S,A_T,\lambda)\) be any suitable decomposition of \(A\). Let \(\Gamma\) be a component of \(B\backslash A\) containing at least two vertices \(c_k\in Y\). If \(d(A_S,c_k)=0\) and \(d(A_T,c_K)=0\) for two vertices \(c_k\in Y\cap V(\Gamma)\) then \(v_{r+1}c_k\in E(B')\) and \(v_{r+2}c_K\in E(B')\). Therefore as \(B\backslash A\triangleleft B'\) it follows that \(v_{r+1}\) and \(v_{r+2}\) belong to the same component of \(B'\). Otherwise, without loss of generality, suppose that \(d(A_S,c_k)=1\) and \(d(A_S,c_K)=1\). Then \(A_S\cup A_T\) has a path component \(P\) with end-vertices \(c_k\) and \(c_K\).

Let \(\cA'\) be the decomposition \(\{A_S',A_T',\lambda\}\) where \(A_S'=(V(B),E_S')\), \(A_T'=(V(B),E_T')\) \[E_S'=E(A_S)\backslash E(P)\cup (E(A_T)\cap E(P))\] \[E_T'=E(A_T)\backslash E(P)\cup (E(A_S)\cap E(P))\] and \(\lambda=(\{\phi(\eps)\},(\phi(\eps)\phi(\eps),1))\). The decomposititon \(\cA'\) has the property that \(d(A_S,c_k)=0\) and \(d(A_T,c_K)=0\). Therefore, by earlier remarks, this decomposition is provisional.

Ryser decompositions of \(\BH\) \[sec2810\]

The aim of this section is to give a useful description of the edge-colourings of \(\BH\) which induce decompositions of \(\BH\) into Ryser proper subgraphs.

\[ex2820\] Returning again to the Ryser \(\eps\)-extension \(\cJ\), shown in Figure \[fig2240\], of the proper \(C_{[7]}\)-edge-coloured \(4\)-free-type simple graph \(\cH\) of order \(8\) shown in Figure \[fig2095\]. It turns out that if \(A\) is the subgraph of \(\BH\) shown in Figure \[fig2610\] then the subgraph \(A'=(V(B),E(B)\backslash E(A))\) is Ryser \(\phi(\eps')\)-proper, where \(\eps'\) is the free-edge of colour \(c_4\).

The edge-coloured graph \(\cB=(B,(\{\alpha,\beta\},\theta))\) where \(\theta\) is defined by \(\theta(e)=\alpha\) if and only if \(e\in E(A)\) and \(\theta(e)=\beta\) if and only if \(e\in E(B)\), shown in Figure \[fig2830\], has some significant properties. The most obvious of these properties is that \(\cB\) is not proper. Other significant properties include the fact that every vertex of degree \(n-r=4\) is the end of either two non-loop edges or a loop of colour \(\alpha\) and of colour \(\beta\), every vertex of degree \(n-r=2\) is the end of at least one edge of colour \(\alpha\) at least one edge of colour \(\beta\) and there is exactly one loop of colour \(\alpha\) and exactly one loop of colour \(\beta\).

see Example \[ex2820\]

Most of the properties of the edge-coloured graph in Figure \[fig2830\] can be described by saying that at each vertex \(u\in V(B)\) satisfying \(d(B,u)\in\{n-r,n-r-2\}\) the degree of \(u\) in every pair of monochromatic induced subgraphs is as equal as possible.

\[def2840\] An \(S\)-edge-colouring \(\phi\) of a multigraph \(G\) is equitable if and only if \(|d(\left\langle \cG,s\right\rangle ,u)-d(\left\langle \cG,t\right\rangle ,u)|\leq 1\) (where \(\cG=(G,\phi)\)) holds for every vertex \(u\in V(G)\) and every pair of colours \(\{s,t\}\subseteq S\). An \(S\)-edge-colouring of a multigraph \(G\) is k-equitable if and only if \(|d(\left\langle \cG,s\right\rangle ,u)-d(\left\langle \cG,t\right\rangle ,u)|\leq 1\) holds for every vertex \(u\in V(G)\) satisfying \(d(G,u)=k\) and every pair of colours \(\{s,t\}\subseteq S\). An edge-coloured graph \(\cG=(G,\phi)\) is (\(k\)-)equitable if and only if \(\phi\) is (\(k\)-)equitable.

In this section \((n-r-2)\)-equitable edge-colourings are of interest. The idea is to colour \(B=\BH\) and take the colour classes as the elements of the decomposition. Equitability is important for ensuring that the elements of the decompositon are Ryser proper graphs. Because the colour classes are intended to induce proper graphs and such graphs have a maximum degree of 2 it follows that the edge-colouring is required to be 2-bounded.

\[def2850\] An \(S\)-edge-colouring \(\phi\) of a multigraph \(G\) is 2-bounded if and only if \(d(\left\langle\cG,s\right\rangle ,u)\leq 2\) for all colours \(s\in S\) and vertices \(u\in V(G)\), where \(\cG=(G,\phi)\). An edge-coloured graph \(\cG=(G,\phi)\) is 2-bounded if and only if \(\phi\) is 2-bounded.

The final important property is that no two loops are coloured the same. In fact this property is a consequence of the edges of \(\BH\) being distributed among the colour classes as evenly as possible. There are exactly \(2|V|\) non-loop edges of each colour and so, if the edges are evenly distributed among the colour classes then because there are the same number of loops as colours. it follows that there is exactly one loop of each colour.

\[def2860\] An \(S\)-edge-colouring \(\phi\) of a multigraph \(G\) is equalised if and only if \(|[\cG,s]|-|[\cG,t]|\leq 1\) holds for every pair of colours \(\{s,t\}\subseteq S\), where \(\cG=(G,\phi)\).

In Lemma \[lem2890\] it is shown that these three properties together are sufficient for an edge-coloured \(\BH\) to have a Ryser proper decomposition.

\[def2870\] If \(F=\{\eps_i\,|\,i\in [(n-r)/2]\}\) then a decomposition \(\{B_i\,|\,i\in [(n-r)/2]\}\) of \(B=\BH\) is proper if and only if \(B_i\) is an \(\eps_i\)-proper graph for all \(i\in [(n-r)/2]\). A proper decomposition \(\{B_i\,|\,i\in [(n-r)/2]\}\) of \(B\) is Ryser if and only if \(B_i\) is a Ryser \(\eps_i\)-proper graph for all \(i\in [(n-r)/2]\).

As shown in the introduction to this thesis, a common method for constructing a decomposition of a graph is to apply the theory of edge-colourings and to take the subgraphs induced by the colour classes as the elements of the decomposition. Here the edge-colourings of interest are those which induce Ryser proper decompositions of \(\BH\).

\[def2880\] An \(S\)-edge-colouring \(\theta\) of \(\BH\) is Ryser proper if and only if \(\{\left\langle\BH, s\right\rangle\,|\, s\in S\}\) is a Ryser proper decomposition of \(\BH\). An edge-coloured multigraph \((B,\theta)\) is Ryser proper if and only if \(\theta\) is Ryser proper.

Lemma \[lem2890\] is the crux of this section and gives a precise description of the edge-colourings which induce Ryser proper decompositions of \(\BH\). This result is introduced so that, in the next section, a result of Häggkvist and Johansson about equalised equitable edge-colourings of nearly-regular graphs can be applied to construct a Ryser proper decomposition of \(\BH\) where this is possible.

\[lem2890\] An \(S\)-edge-colouring \(\theta\) of \(\BH\) is Ryser proper if and only if \(|S|=(n-r)/2\) and \(\theta\) is 2-bounded, equalised and \((n-r-2)\)-equitable.

Suppose \(\theta\) is a Ryser proper \(S\)-edge-colouring of \(B=\BH\) and \(\cB=(B,\theta)\). Then, by definition, \(\{\left\langle\cB, s\right\rangle\,|\, s\in S\}\) is a Ryser proper decomposition of \(\BH\). Therefore, by definition, if \(F=\{\eps_i\,|\,i\in [(n-r)/2]\}\) then \(\{\left\langle\cB, s\right\rangle\,|\, s\in S\}=\{B_i\,|\,i\in [(n-r)/2]\}\) where \(B_i\) is Ryser \(\phi(\eps_i)\)-proper for all \(i\in [(n-r)/2]\).

As \(|S|=|\{\left\langle\cB, s\right\rangle\,|\, s\in S\}|\) it follows that \(|S|=(n-r)/2\). By Lemma \[lem2630\] (\[lem26301\]) it follows that \(\Delta(B_i)=2\) for all \(i\in [(n-r)/2]\). Therefore \(\theta\) is 2-bounded. By Lemma \[lem2630\] (\[lem26303\]) it follows that \(|E(B_i)|=2r+1\) for all \(i\in [(n-r)/2]\). Therefore \(\theta\) is equalised. If \(d(B,u)=n-r-2\) then \(u\in C\) and by Lemma \[lem2730\] (\[lem27302\]) it follows that \(d(B_i,u)\geq 1\) for all \(i\in [(n-r)/2]\). Therefore, as \(\theta\) is 2-bounded it follows that \(d(B_i,u)\in\{1,2\}\) for all \(i\in [(n-r)/2]\). Hence \(\theta\) is \((n-r-2)\)-equitable.

Now suppose \(\theta\) is a 2-bounded, equalised, \((n-r-2)\)-equitable \(S\)-edge-colouring of \(B=\BH\) and \(|S|=(n-r)/2\). Let \(F=\{\eps_i\,|\,i\in [(n-r)/2]\}\) and \(L(B)=\{\lambda_i\,|\,i\in [(n-r)/2]\}\) be such that \(\lambda_i\) has \(\phi(\eps_i)\) as an end for all \(i\in [(n-r)/2]\) and let \(S=\{s_i\,|\,i\in [(n-r)/2]\}\) be such that \(\theta(\lambda_i)=s_i\) for all \(i\in [(n-r)/2]\). Let \(B_i=\left\langle\cB, s_i\right\rangle\), where \(\cB=(B,\theta)\), for all \(i\in [(n-r)/2]\).

As \(\theta\) is 2-bounded and \(|S|=(n-r)/2\) it follows that if \(d(B,u)=n-r\) then \(d(B_i,u)=2\) and \(\Delta(B_i)=2\) for all \(i\in [(n-r)/2]\). As every edge of \(B\) is either a non-loop edge with an end in \(V\) or a loop, of which there are \((n-r)/2\), it follows that \(|E(B)|=r(n-r)+(n-r)/2=((n-r)/2)(2r+1)\). Therefore, as \(\theta\) is equalised and \(S=(n-r)/2\) it follows that \(E(B_i)=2r+1\) for all \(i\in [(n-r)/2]\). By definition \(\lambda_i=(\phi(\eps_i)\phi(\eps_i),1)\in E(B_i)\) for all \(i\in [(n-r)/2]\). Therefore, for all \(i\in [(n-r)/2]\), \(B_i\) is, by Lemma \[lem2630\], a \(\phi(\eps_i)\)-proper graph.

As \(\theta\) is \((n-r-2)\)-equitable it follows that if \(d(B,u)=n-r-2\) then \(d(B_i,u)\geq 1\) for all \(i\in [(n-r)/2]\). Indeed, if \(d(B_i,u)=0\) for some \(i\in [(n-r)/2]\) then, as \(|S|=(n-r)/2\), it follows that there exists some \(j\in [(n-r)/2]\backslash\{i\}\) such that \(d(B_j,u)=2\) and therefore that \(\theta\) is not \((n-r-2)\)-equitable. A contradiction.

By Lemma \[lem2630\] and Lemma \[lem2730\] it follows from the preceeding three paragraphs that \(B_i\) is a Ryser \(\phi(\eps_i)\)-proper graph for all \(i\in [(n-r)/2]\). Therefore, by definition, \(\cB\) is a Ryser proper decomposition of \(B\) and consequently, \(\theta\) is a Ryser proper edge-colouring of \(B\).

\(B\)-type graphs, proper-type subgraphs and Ryser-type decompositions \[sec3080\] In Section \[sec3227\] the aim is to show that an \((n-r)\)-Ryser proper \(C\)-edge-coloured \(r\)-free-type simple graph \(\cH\) of even order \(n\) has an \((n-r-2)\)-good Ryser proper \(\eps\)-extension for some \(\eps\in F\). The results of Section \[sec3227\] are used, in Section \[sec3260\], to prove the main result of this chapter and also in Section \[sec5420\] of Chapter 3 to prove one of the main results of that chapter. As a consequence, the aim of this section is to generalise much of what has preceeded so that the results of Section \[sec3227\] can be applied in Section \[sec5420\]. Instead of talking explicitly about the multigraph \(\BH\), in Section \[sec3227\] the results are proved for \(B\)-type multigraphs, of which \(\BH\) is an instance.

\[def3090\] A multigraph \(G\) is –type if and only if \(V(G)=P\cup Q\), where \(|P|=p\) and \(|Q|=q\), \(G\) has exactly \((q-p+1)/2\) loops (and hence \(p\equiv q-1\bmod{2}\)) all of which have their ends in \(Q\), every non-loop edge of \(G\) has an end in \(P\) and an end in \(Q\) and (\[def30901\])-(\[def30903\]) hold.

1. \(\Delta(G)=q-p+1\) \[def30901\]

2. \(d(G,v)=q-p+1\) for all \(v\in P\) \[def30902\]

3. \(d(G,v)\equiv q-p+1\bmod{2}\) for all \(v\in Q\) \[def30903\]

\[ex3100\] The (multi)graph in Figure \[fig2390\] is \((4,7)\)-\(B\)-type.

Example \[ex3100\] is an special case of the obviously general fact that \(B(\cH)\) is \((r,n-1)\)-\(B\)-type if \(\cH\) is Ryser.

\[lem3110\] If \(\cH\) is a Ryser proper \(C\)-edge-coloured \(r\)-free-type simple graph of even order \(n\) then \(\BH\) is \((r,n-1)\)-\(B\)-type.

By definition \(B=\BH\) has a vertex partition \(V(B)=V\cup C\), where \(|V|=r\) and \(|C|=n-1\), with the property that \(B\) has \((n-r)/2\) loops all of which have their ends in \(C\). Moreover, every non-loop edge of \(\BH\) has an end in \(V\) and an end in \(C\). From Lemma \[lem2430\] it follows, as \(\cH\) is Ryser and therefore \(\xk\geq 0\) for all \(c_k\in C\), that \(\Delta(B)=n-r\), \(d(B,v)=n-r\) for all \(v\in V\) and \(d(B,c_k)=(n-r)-2\xk\equiv n-r\bmod{2}\) for all \(c_k\in C\). Therefore \(B\) is \((r,n-1)\)-\(B\)-type.

So far in this chapter the interest in \(\BH\) has centered around finding Ryser proper decompositions. In Definitions \[def3120\]-\[def3140\] this kind of decomposition is generalised for \(B\)-type multigraphs.

\[def3120\] If \(B\) is a \((p,q)\)-\(B\)-type multigraph and \(v\in Q\) then a -suitable-type graph is a graph \(A\triangleleft \BH\) which satisfies (\[def31201\]),(\[def31202\]) and (\[def31203\]).

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

2. \(d(A,u)=1\) for all \(u\in P\) \[def31202\]

3. \(d(A,v)=0\) \[def31203\]

\[def3130\] If \(B\) is a \((p,q)\)-\(B\)-type multigraph and \(v\in Q\) then a -proper-type graph is a subgraph \(A\triangleleft \BH\) which satisfies (\[def31301\])-(\[def31304\]).

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

2. \(d(A,u)=2\) for all \(u\in P\) \[def31302\]

3. \(|E(A)|=2p+1\) \[def31303\]

4. \((vv,1)\in E(A)\) \[def31304\]

\[def3140\] A \(v\)-proper-type graph \(A\) is Ryser if and only if (\[def31401\]) and (\[def31402\]) both hold.

1. If \(d(B,u)=q-p+1\) then \(d(A,u)=2\) for all \(u\in Q\) \[def31401\]

2. If \(d(B,u)=q-p-1\) then \(d(A,u)\geq 1\) for all \(u\in Q\)\[def31402\]

A consequence of Lemma \[lem2630\] is that graphs which correspond to \(\phi(\eps)\)-proper pairs have suitable decompositions. In the Definition \[def3150\] this kind of decomposition is generalised for proper-type graphs.

\[def3150\] A decomposition \(\cA\) of a \(v\)-proper-type graph \(A\) is a suitable-type decomposition if and only if \(\cA=\{A_1,A_2,\lambda\}\) where \(A_1\) and \(A_2\) are both \(v\)-suitable-type subgraphs and \(\lambda=(\{v\},(vv,1))\).

\[def3180\] A suitably decomposed -proper-type graph is a pair \((A,\cA)\) where \(A\) is a \(v\)-proper-type subgraph of \(B\) and \(\cA\) is a suitable decomposition of \(A\).

If \(\cJ\) is an extension of \(\cH\) then the graph \(\BJ\) obviously has a close relationship with the graph \(\BH\). This relationship is generalised, in Definition \[def3160\], for \(B\)-type multigraphs.

\[def3160\] If \(\cA=\{A_1,A_2,\lambda\}\) is a suitable-type decomposition of a \(v\)-proper-type graph \(A\) and \(v',v''\notin V(B)\) then \(B'=B'(A,\cA,v',v'')\) is the multigraph with vertex-set \(V(B')=V(B)\cup\{v',v''\}\) and edge-set \(E(G')=(E(G)\backslash E(A))\cup E_{v'}\cup E_{v''}\) where \(E_{v'}=\{v'u\,|\,u\in Q\backslash\{v\}\mbox{ and } d(A_1,u)=0\}\) and \(E_{v''}=\{v''u\,|\,u\in Q\backslash\{v\}\mbox{ and } d(A_2,u)=0\}\).

\[lem3170\] If \(\cJ\) is the \(\eps\)-extension of \(\cH\) corresponding to a suitable decompositon \(\cA\) of a \(\phi(\eps)\)-proper graph \(A\) then \(\BJ=B'(A,\cA,v_{r+1},v_{r+2})\).

Let \(B=\BH\), \(B'=B'(A,\cA,v_{r+1},v_{r+2})\) and \(B''=\BJ\). Then, by definition, \(V(B')=V_{[r+2]}\cup C\) and \(V(B'')=V_{[r+2]}\cup C\). So \(B'=B''\) if and only if \(E(B')=E(B'')\).

By definition, \(E(B')=E(B)\backslash E(A)\cup E'\cup E''\) where \(E'=\{v_{r+1}c_k\,|\,c_k\in C\backslash\{\phi(\eps)\}\mbox{ and }d(A_1,c_k)=0\}\) and \(E''=\{v_{r+2}c_k\,|\,c_k\in C\backslash\{\phi(\eps)\}\mbox{ and }d(A_2,c_k)=0\}\), where \(\cA=\{A_1,A_2,\lambda\}\). By definition \(E(B'')=\{v_ic_k\,|\,v_i\in V_{[r+2]}, c_k\in M(\cJ,v_i)\}\cup\{(c_kc_k,\eps(\cJ,c_k))\,|\,c_k\in C\}\).

Now, as \(E'\) and \(E''\) contain no loops it follows that \(L(B')=L(B)\backslash L(A)=\{(c_kc_k,\eps(\cH,c_k))\,|\,c_k\in C\backslash\{\phi(\eps)\}\}\cup\{\phi(\eps)\phi(\eps)\,|\,\eps(\cH,c_k)-1\}\). Now, because \(\eps(\cJ,c_k)=\eps(\cH,c_k)\) for all \(c_k\in C\) and \(\eps(\cJ,c_k)=\eps(\cH,\phi(\eps)-1)\) it follows that \(L(B')=L(B'')\).

It remains to show that every non-loop edge \(e\in E(B')\) is an non-loop edge of \(B''\) and every non-loop edge \(e\in E(B'')\) is a non-loop edge of \(B'\).

If \(e\in E(B')\) is a non-loop edge then \(e=v_ic_k\) for some \(v_i\in V_{[r+2]}\). If \(i\in [r]\) then \(v_ic_k\in E(B)\backslash E(A)\). Therefore, \(c_k\in M(\cH,v_i)\) and because \(d(A,c_k)=0\) it follows that \(c_k\in M(\cJ,v_i)\). Therefore \(v_ic_k\in E(B'')\). If \(v_i=v_{r+1}\) then \(c_k\in C\backslash\{\phi(\eps)\}\) and \(d(A_1,c_k)=0\). It follows that, \(c_k\in M(\cJ,v_i)\) and therfore \(v_ic_k\in E(B'')\). If \(v_i=v_{r+2}\) then \(c_k\in C\backslash\{\phi(\eps)\}\) and \(d(A_2,c_k)=0\). It follows that, \(c_k\in M(\cJ,v_i)\) and therefore \(v_ic_k\in E(B'')\).

If \(v_ic_k\in E(B'')\) and \(i\in [r]\) then, as \(c_k\in M(\cJ,v_i)\) it follows, as \(M(\cJ,v_i)\subset M(\cH,v_i)\), that \(v_ic_k\in E(B')\). If \(i=r+1\) then, as \(c_k\in M(\cJ,v_i)\) it follows that \(d(A_1,c_k)=0\) and therefore \(v_ic_k\in E'\subset E(B')\). If \(i=r+2\) then, as \(c_k\in M(\cJ,v_i)\) it follows that \(d(A_2,c_k)=0\) and therefore \(v_ic_k\in E''\subset E(B')\).

Provisional extensions are crucial to the proof of Theorem \[thm3270\] and are generalised in Definition \[def3190\].

\[def3190\] A suitably decomposed \(v\)-proper-type graph \((A,\cA)\) is provisional if and only if for every pair of vertices \(\{v',v''\}\nsubseteq V(B)\) \(v'\) and \(v''\) are vertices of the same component of \(B'(A,\cA,v',v'')\).

\[def3200\] If \((A,\cA)\) is a suitably decomposed \(v\)-proper-type graph then \(\boldmath{S}=S(A,\cA,v',v'')\) is the component of \(B'=B'(A,\cA,v',v'')\) containing \(v'\) and \(v''\) and \(\boldmath{T}=T(A,\cA,v',v'')=(V(B')\backslash V(S),E(B')\backslash E(S))\).

\[def3210\] A decomposition \(\cB\) of a \((p,q)\)-\(B\)-type multigraph \(B\) is a proper-type decomposition if and only if \(|\cB|=(q-p+1)/2\) and, for all \(A\in\cB\), \(A\) is a \(v\)-proper-type subgraph of \(B\) for some \(v\in Q\).

\[def3220\] A proper-type decomposition \(\cB\) of a \((p,q)\)-\(B\)-type multigraph \(B\) is Ryser if and only if \(A\) is Ryser, for all \(A\in\cB\).

In the Section \[sec2900\] bad components are of interest.

\[def3225\] A component of a \((p,q)\)-\(B\)-type multigraph \(B\) is -bad if and only if there exists \(u\in V(B)\) such that \(d(B,u)=q-p-1\) and \(d(B,v)=p-1+1\) for all \(v\in V(B)\backslash\{u\}\).

Finding Ryser proper edge-colourings \[sec2900\] In this section the aim is to show that \(\cH\) is semi-completable if and only if \(\cH\) is Ryser and \((n-r)\)-good. The approach taken is to show that \(\BH\) has a Ryser proper edge-colouring if and only if \(\cH\) is Ryser and \((n-r)\)-good. This is proved by applying Theorem \[thm2920\], due to Häggkvist and Johannson, about equitable edge-colourings of nearly-regular multigraphs to a safe embedding of \(\BH\).

\[def2910\] A multigraph \(G\) is connected if and only if \(G\) has exactly one component.

\[Häggkvist and Johannson @MR95f:05091\] \[thm2920\] Let \(G\) be a connected multigraph such that all vertices have degree \(2k\), \(2k-1\) or \(2k-2\). Then \(G\) has an equalised, equitable \(S\)-edge-colouring, where \(|S|=k\), if and only if \(G\) has at least one vertex of degree \(2k-1\) or the number of vertices of degree \(2k-2\) in \(G\) is either zero or at least two and not an odd number if \(k=2\).

As the maximum degree of \(\BH\) is \(n-r\), and an edge-colouring with \((n-r)/2\) colours is sought, it makes sense to apply Theorem \[thm2920\] with \(k=(n-r)/2\). In fact this is the only value of \(k\) for which Theorem \[thm2920\] is applied in this thesis.

As \(\BH\) has no vertices of degree \(n-r-1\) Theorem \[thm2920\] reduces to the statement that a component \(\Lambda\) of \(\BH\) has an equitable edge-colouring if and only if \(\Lambda\) has zero or at least two vertices of degree \(n-r-2\) and not an odd number if \(n-r=4\).

\[def2930\] If \(G\) is a multigraph then a component \(\Lambda\) of \(G\) is an -bad component if and only if \(2k>4\) and there exists \(u^{\star}\in V(\Lambda)\) such that \(d(G,u)=2k\) for all \(u\in V(\Lambda)\backslash\{u^{\star}\}\) and \(d(G,u^{\star})=2k-2\).

The reason for not including the other case when \(n-r=4\) is that in that case, as is shown in Lemma \[lem3040\], \(\BH\) has an \((n-r)\)-bad component as defined here.

In one respect Theorem \[thm2920\] is stronger than needed because \(\BH\) has no vertices of degee \(n-r-1\). On the other hand it is not strong enough because \(\BH\) may have vertices of degree other than \(n-r\) or \(n-r-2\). However, this apparent weakness can be circumvented by embedding \(\BH\) in a graph which has only vertices of degree \(n-r\) and \(n-r-2\). This embedding may of course be the trivial one of \(\BH\) in itself.

An important property for the embedding \(B^{\star}=B^{\star}(\cH)\) of \(B=\BH\) is that no edge of \(E(B^{\star})\backslash E(B)\) has a vertex of degree \(u\in V(B)\) satisfying \(d(B,u)=n-r\) or \(d(B,u)=n-r-2\) as an end. The reason for this is that Theorem \[thm2920\] is used to obtain an equitable edge-colouring of \(B^{\star}\) which, restricted to the edges of \(B\) is \((n-r-2)\)-equitable.

\[def2940\] A \((p,q)\)-\(B\)-type multigraph \(B\) is safely embedded in a multigraph \(B^{\star}\) if and only if no edge \(e\in E(B^{\star})\cap E(B)\) has a vertex \(u\) as an end if \(d(B,u)\in\{n-r,n-r-2\}\).

The embedding \(B^{\star}\) of \(B\) of interest is constructed by introducing two sets of vertices \(V^{\star}\) and \(C^{\star}\) (both possibly empty) to \(B\). Edges with ends in \(V^{\star}\) and \(C^{\star}\) or \(V^{\star}\) and \(C\) are then introduced. For each stable colour \(c_k\) which is not an isolated vertex of \(B\) there is a set of vertices in \(V^{\star}\), along with a set of equal size in \(C^{\star}\),

\[def2950\] If \(B\) is a \((p,q)\)-\(B\)-type multigraph and \(d(B,v)\in\{0,q-p-1,q-p+1\}\) then \(P^{\star}(v)=\emptyset\) and \(Q^{\star}(v)=\emptyset\), otherwise \[\label{eqn2950} P^{\star}(v)=\{u^{\star}_{k,i}\,|\, i\in [(q-p-1-d(B,v))/2]\}\] \[\label{eqn2950} Q^{\star}(v)=\{v^{\star}_{k,i}\,|\, i\in [(q-p-1-d(B,v))/2]\}\]

The idea is to join each vertex in \(P^{\star}(v)\) to \(v\) by two edges and to a vertex in \(Q^{\star}\) by \(q-p-1\) edges. As there are \((q-p-1-d(B,v))/2\) vertices in \(P^{\star}(v)\) the degree of \(v\) increases by \(q-p-1-d(B,v)\) making \(v\) a vertex of degree \(q-p-1\) in \(B^{\star}\). Then every vertex in \(P^{\star}(v)\) has degree \(q-p+1\) and every vertex in \(C^{\star}(v)\) has degree \(q-p-1\). This is repeated for every vertex \(v\) to give the desired safe embedding.

\[def2960\] If \(B\) is a \((p,q)\)-\(B\)-type multigraph and \(d(B,v)\in\{0,q-p-1,q-p+1\}\) then \(E^{\star}(v)=\emptyset\), otherwise \[\label{eqn2960} E^{\star}(v)=\{(u^{\star}_{k,i}v,2),(u^{\star}_{k,i}v^{\star}_{k,i},n-r-2)\,|\,i\in [(q-p-1-d(B,v))/2]\}\]

\[def2970\] If \(F\in\{P,Q,E\}\) then \[\label{eqn2840} F^{\star}=\bigcup_{v\in Q}F^{\star}(v)\]

\[def2980\] If \(q-p\leq 3\) let \(B^{\star}=B\) and if \(q-p\geq 5\) let \(B^{\star}\) be the mulltigraph with vertex set \(V(B^{\star})=V(B)\cup V^{\star}\cup C^{\star}\) and edge-set \(E(B^{\star})=E(B)\cup E^{\star}\).

\[lem2990\] If \(B\) is a \((p,q)\)-\(B\)-type multigraph then \(B^{\star}\) is a safe embedding of \(B\) and every vertex of \(B^{\star}\) either has degree \(q-p+1\) or degree \(q-p-1\).

By definition \(B^{\star}\) is an embedding of \(B\). It is safe because only vertices \(v\) which satisfy \(0<d(B,c_k)\leq q-p-3\) are the ends of edges in \(E(B^{\star})\backslash E(B)\). If \(v\in Q\) satisfies \(d(B,v)\in\{q-p-1,q-p+1\}\) then \(d(B^{\star},v)\in\{q-p-1,q-p+1\}\). If \(v\in Q\) satisfies \(0<d(B,v)\leq q-p-3\) then \(d(B^{\star},v)=q-p-1\). If \(v\in V^{\star}\) then \(d(B^{\star},u)=q-p+1\) if \(u\in C^{\star}\) then \(d(B^{\star},u)=q-p-1\).

\[ex3000\] If \(\cH\) is the proper \(C_{[9]}\)-edge-coloured \(4\)-free-type simple graph of order \(10\) in Figure \[fig3010\] then the graph in Figure \[fig3020\] is \(\BS\).

see Ex \[ex3000\]

see Ex \[ex3000\]

The idea now is to show that \(\BH\) has a Ryser proper edge-colouring if and only if \(\cH\) is Ryser and \((n-r)\)-good. The main tools used to prove this are the safe embedding of \(\BH\) in \(\BS\) and Theorem \[thm2920\]. Before this is proved, in Lemma \[lem3060\], some other results are proved which make the proof of Lemma \[lem3060\] less of a chore. The first of these is Lemma \[lem3030\]. It is shown in Lemma \[lem3030\] that a Ryser proper \(C\)-edge-coloured \(r\)-free-type simple graph \(\cH\) of even order \(n\) is \((n-r)\)-bad if and only if \(\BH\) contains an \((n-r)\)-bad component.

\[lem3030\] If \(\cH\) is a Ryser proper \(C\)-edge-coloured \(r\)-free-type simple graph of even order \(n\) then \(\cH\) is \((n-r)\)-bad if and only if \(\BH\) contains an \((n-r)\)-bad component.

If \(\cH\) is \((n-r)\)-bad then, by definition, there is a set of colours \(S\subset C\) which satisfies \(\wone=1\), \(\wtwoplus=0\), \(\p=1\) and \(\eps(\cH,S)=(n-r-2)/2\). Therefore \(S\) is a set of vertices of \(B=\BH\) all of which satisfy \(d(B,c_k)=n-r\) except for exactly one, \(c_z\) say, which satisfies \(d(B,c_z)=n-r-2\).

Therefore the number of edges in \(E(\BH)\) of the form \(v_ic_k\) with \(c_k\in S\) and \(v_i\in N(S)\) is \(d(S)-(n-r-2)\) and \(d(S)-(n-r-2)=(|S|-1)(n-r)+(n-r-2)-(n-r-2)=(|S|-1)(n-r)=d(N(S))\). It follows that every edge with an end in \(N(S)\) also has an end in \(S\). Therefore, if \(\Lambda\) is the component of \(\BH\) containing \(c_z\) all the vertices in \(V(\Lambda)\) are in \(S\cup N(S)\) and hence every vertex \(c_k\in V(\Lambda)\) satisfies \(d(B,c_k)=n-r\) except for \(c_z\) which satisfies \(d(B,c_z)=n-r-2\). Therefore \(\Lambda\), by definition, is an \((n-r)\)-bad component.

Now suppose \(\BH\) contains an \((n-r)\)-bad component \(\Lambda\). Let \(S=V(\Lambda)\cap C\). As \(\Lambda\) is \((n-r)\)-bad if follows, by definition and from Lemma \[lem2430\], that \(\wone=1\) and \(\wtwoplus=0\). As the number of edges of the form \(vc\) with \(c\in S\) and \(v\in N(S)\) is \(d(S)-2\eps(S)=(|S|-1)(n-r)+(n-r-2)-2\eps(S)\) it follows that \((|S|-1)(n-r)\leq d(N(S))< (|S|-2)(n-r)\) therefore \(d(N(S))=(|S|-1)(n-r)\) and so \(|N(S)|=|S|-1\) or \(\p=1\). Finally, as \(d(S)=(|S|-1)(n-r)+n-r-2\) it follows that \(2\eps(S)=n-r-2\) and so \(\eps(S)=(n-r-2)/2\).

Theorem \[thm2920\] can only be applied with \(k=(n-r)/2=2\) if there is no component with an odd number of vertices of degree \(n-r-2=2\). It turns out, proved next in Lemma \[lem3040\], that if \(n-r=4\) then \(\BH\) only has such a component if \(\BH\) also has a \(4\)-bad component.

\[lem3040\] If \(q-p=3\), \(B\) is a \((p,q)\)-\(B\)-type multigraph and every component of \(B\) is \((q-p+1)\)-good then every component of \(B\) has an even number of vertices \(v\) which satisfy \(d(B,v)=q-p-1\).

As \(B\) has exactly \((q-p+1)/2\) loops each of which has its end in \(C\) it follows that \(d(B,V)=d(B,C)-(q-p+1)\). Because \(B\) is \((p,q)\)-\(B\)-type it follows that \(d(B,u)=q-p+1\) for all \(u\in P\), \(d(B,v)\leq q-p+1\) for all \(v\in Q\) and \(d(B,v)\equiv q-p+1\bmod{2}\) for all \(v\in Q\). Therefore \(d(B,P)=p(q-p+1)\) and \(d(B,v)=q-p+1-2x(v)\) for all \(v\in V\) where \(x(v)\geq 0\). Therefore \(d(B,Q)=q(q-p+1)-2x(Q)\) and hence \(x(Q)=(q-p-1)(q-p+1)/2=4\).

Now, if \(B\) has a component \(\Lambda\) which has \(2m-1>1\) vertices \(v\) which satisfy \(d(B,v)=2\) it follows that \(m=2\) and, because \(x(Q)=4\), it follows that \(B\) contains exactly one further vertex \(v^{\star}\in V(B)\backslash V(\Lambda)\) satisfying \(d(B,v^{\star})=2\) and every other vertex \(v\in V(B)\backslash V(\Lambda)\) has satisfies \(d(B,v)=4\). The component of \(B\) containing vertex \(v^{\star}\) is, therefore, a \((q-p+1)\)-bad component.

Of course it is proposed to apply Thm \[thm2920\] not to \(\BH\) but to \(B^{\star}(\cH)\). Fortunately, as is shown in Lemma \[lem3050\], \(B^{\star}\) is constructed so as not to have an \((n-r)\)-bad component unless \(B\) does.

\[lem3050\] If \(B\) is a \((p,q)\)-\(B\)-type multigraph and every component of \(B\) is \((q-p+1)\)-good then every component of \(B^{\star}\) is \((q-p+1)\)-good.

If \(\Lambda\) is a component of \(B^{\star}\) and \(V(\Lambda)\) contains a vertex \(v\) which satisfies \(d(B,v)<q-p-1\) then, by the definition of \(B^{\star}\) it follows that \(d(v_{k,i}^{\star})=q-p-1\) for all \(i\in [(q-p-1-d(B,v))/2]\) and \(d(B^{\star},v)=d(B,v)+q-p-1-d(B,v)=q-p-1\). It follows that \(\Lambda\) contains at least two vertices of degree \(q-p-1\) and therefore \(\Lambda\) is not \((q-p+1)\)-bad.

Otherwise every vertex \(u\in V(\Lambda)\) satisfies \(d(B,u)\geq q-p-1\) and so, by the definition of \(B^{\star}\), it follows that \(d(B^{\star},u)=d(B,u)\). Therefore, if \(\Lambda\) is a \((q-p+1)\)-bad component of \(B^{\star}\) it follows that \(\Lambda\) is a \((q-p+1)\)-bad component of \(B\).

The next lemma is the most important result of this section and is crucial in proving Theorem \[thm3270\], the central result of this chapter. It says that being \((n-r)\)-good suffices for a Ryser edge-colouring of \(\BH\).

\[lem3060\] If \(\cB\) is a \((p,q)\)-\(B\)-type multigraph then \(B\) has a Ryser proper-type \(S\)-edge-colouring if and only if every component of \(B\) is \((q-p+1)\)-good.

First suppose that \(B\) has a Ryser proper-type \(S\)-edge-colouring \(\theta\). By definition \(\theta\) is 2-bounded and \(S=(q-p+1)/2\), therefore if \(\cB=(B,\theta)\) and \(u\in V(B)\) satisfies \(d(B,u)=q-p+1\) then \(d(\left\langle\cB,s\right\rangle,u)=2\) for all \(s\in S\). Now, because \(\theta\) is also \((q-p+1)\)-equitable, if \(\Lambda\) is a component of \(B\) such that \(d(B,u)\in\{q-p+1,q-p-1\}\) for all \(u\in V(\Lambda)\) then \(\theta|_{\Lambda}:E(\Lambda)\rightarrow S\), defined by \(\theta|_{\Lambda}(e)=\theta(e)\) for all \(e\in E(\Lambda)\), is an equitable edge-colouring of \(\Lambda\). Therefore, by Theorem \[thm2920\] \(\Lambda\) is \((q-p+1)\)-good. It follows that every component of \(B\) is \((q-p+1)\)-good and therefore, by Lemma \[lem3030\] \(\cH\) is \((q-p+1)\)-good.

Now suppose every component of \(B\) is \((q-p+1)\)-good. Then, by Lemma \[lem3040\], if \(q-p=3\) every component of \(B\) has an even number of vertices \(v\) which satisfy \(d(B,v)=q-p-1\). By Lemma \[lem2990\] \(B\) has a safe embedding in a multigraph \(B^{\star}\), where \(d(B^{\star},u)\in\{q-p+1,q-p-1\}\) for all \(u\in V(B^{\star})\). By Lemma \[lem3050\] it follows that \(B^{\star}\) has no \((q-p+1)\)-bad component. Moreover, if \(q-p=3\), then as \(B^{\star}=B\) it follows that every component of \(B^{\star}\) has an even number of vertices of degree \(q-p-1\).

Now by Theorem \[thm2920\] it follows that every component \(\Lambda\) of \(B^{\star}\) has an equalised equitable \(S\)-edge-colouring \(\theta_{\Lambda}\), where \(|S|=(q-p+1)/2\). As \(\theta_{\Lambda}\) is equalised it follows that in the edge-coloured graph \((\Lambda,\theta_{\Lambda})\) there is at most one loop of colour \(s\) for all \(s\in S\). Consequently there exists an equalised equitable \(S\)-edge-colouring \(\theta\) of \(B^{\star}\).

Now let \(\theta|_B:E(B)\rightarrow S\) be the edge-colouring of \(B\) defined by \(\theta|_B(e)=\theta(e)\) for all \(e\in E(B)\cap E(B^{\star})\). As \(B^{\star}\) is a safe embedding of \(B\) it follows, as \(\theta\) is equitable, that \(\theta|_B\) is \((q-p-1)\)-equitable. As \(\theta\) is 2-bounded and \(d(\left\langle (B,\theta|_B),s\right\rangle,u)\leq d(\left\langle (B^{\star},\theta),s\right\rangle,u)\) for all \(u\in V(B)\) it follows that \(\theta|_B\) is 2-bounded. Finally as there is exactly one loop of colour \(s\) in \(\cB=(B,\theta|_B)\) and \(d(\left\langle\cB,s\right\rangle,v)=2\) for all \(v\in V\) and \(s\in S\) it follows that \(|[\cB,s]|=2|V|+1\) for all \(s\in S\). Therefore \(\theta|_B\) is also equalised.

By definition, \(\BH\) has a Ryser proper decomposition if and only if \(\cH\) is semi-completable. This implies Corollary \[cor3070\].

\[cor3070\] A Ryser proper \(C\)-edge-coloured \(r\)-free-type simple graph \(\cH\) of even order \(n\) is semi-completable if and only if \(\cH\) is \((n-r)\)-good.

Also, if \(\cH\) is semi-completable then, trivially, \(\cH\) is also fully Ryser extendible, this, along with the observation that if \(\cH\) is \((n-r)\)-bad then \(\cH\) is not fully Ryser extendible, implies Corollary \[cor3075\]

\[cor3075\] A Ryser proper \(C\)-edge-coloured \(r\)-free-type simple graph \(\cH\) of even order \(n\) is fully Ryser extendible if and only if \(\cH\) is \((n-r)\)-good.

In this section some useful tools have been developed. The most significant of which is Lemma \[lem3060\] which gives an necessary and sufficient conditions for the possibility of decomposing \(\BH\) into Ryser proper subgraphs. In the next section the question of whether it is always possible to extend an \((n-r)\)-good Ryser proper \(C\)-edge-coloured \(r\)-free-type simple graph \(\cH\) of even order \(n\) to an \((n-r-2)\)-good Ryser proper \(C\)-edge-coloured \(r\)-free-type simple graph of even order \(n\) is addressed.

A key general result \[sec3227\]

The aim of this section is to prove Lemma \[lem3250\] which is the key to the proof of Theorem \[thm3270\] in Section \[sec3260\]. Lemma \[lem3250\] is also the key to the proof of Theorem \[thm5550\] in Section \[sec5420\] of Chapter 3. For this reason the generalised language of Section \[sec3080\] is maintained in this section.

\[lem3230\] If \(\cB\) is a Ryser proper-type decomposition of a \((p,q)\)-\(B\)-type multigraph \(B\) and \((A,\cA)\) is a suitably decomposed Ryser \(v\)-proper graph with \(A\in\cB\), then every component of \(T(A,\cA,v',v'')\) is \((q-p-1)\)-good.

Let \(\theta:E(T)\rightarrow\cB\backslash A\) be the edge-colouring defined by \(\theta(e)=D\) if and only if \(e\in E(D)\).

If \(u\in V(T)\cap P\) then, as \(D\) is \(v(D)\)-proper-type for all \(D\in\cB\backslash A\) it follows, from Definition \[def3130\] (\[def31301\]) that \(d(D,u)=2\) for all \(D\in\cB\backslash A\). If \(u\in V(T)\cap Q\) satisfies \(d(B,u)=q-p-1\) then, as \(\cB\) is Ryser it follows, by definition, that \(d(D,u)=2\) for all \(D\in\cB\backslash A\). Therefore \(\theta\) is \((q-p-1)\)-equitable.

If \(u\in V(T)\) satisfies \(d(T,u)=q-p-3\) then, as \(B'=B'(A,\cA,v',v'')\) is \((p+2,q)\)-\(B\)-type it follows, by definition, that \(u\in V(T)\cap Q\). Therefore, as \(\cB\) is Ryser it follows that \(d(D,u)\geq 1\) for all \(D\in\cB\backslash A\). Therefore, as \(D\) is \(v(D)\)-proper for all \(D\in\cB\backslash A\) it follows that \(\Delta(D)\leq 2\) for all \(D\in\cB\backslash A\) and, consequently, \(\theta\) is \((q-p-3)\)-equitable.

Therefore, if \(T\) has a component \(\Lambda\), such that every vertex \(u\in V(\Lambda)\) satisfies \(d(T,u)\in\{q-p-1,q-p-3\}\) it follows that \(\theta|_{\Lambda}\) is an equitable \(\cB\backslash A\)-edge-colouring of \(\Lambda\). As \(|\cB\backslash A|=(q-p-1)/2\) it follows by Theorem \[thm2920\] that \(\Lambda\) is \((q-p-1)\)-good.

\[lem3240\] If \(B\) is \((p,q)\)-\(B\)-type and \(B\) has a \((q-p+1)\)-bad component \(\Gamma\) then \(E(\Gamma)\) contains exactly \((q-p-1)/2\) loops and \(E(B)\backslash E(\Gamma)\) contains exactly one loop and \(|V(\Gamma)\cap P|=|V(\Gamma)\cap Q|-1\).

Let \(P_{\Gamma}=V(\Gamma)\cap P\), \(Q_{\Gamma}=V(\Gamma)\cap Q\), \(x=|P_{\Gamma}|\) and \(y=|Q_{\Gamma}|\). As \(d(\Gamma,u)=q-p+1\) for all \(u\in P_{\Gamma}\) and \(d(\Gamma,u)\leq q-p+1\) for all \(u\in Q_{\Gamma}\) it follows that \(y\geq x\). Also, because every edge of \(\Gamma\) either has an end in \(P\) or is a loop with an end in \(Q\) it follows that \(2|E(\Gamma)|=x(q-p+1)+2z\), where \(z\) denotes the number of loops in \(E(\Gamma)\).

Every edge of \(\Gamma\) has an end in \(Q_{\Gamma}\) and, because \(\Gamma\) is \((q-p+1)\)-bad it follows that \(2|E(\Gamma)|=(q-p+1)(y-1)+(q-p-1)\). Therefore \(2z=(q-p+1)(y-x-1)+(q-p-1)\). Now, because \(z\geq 0\) it follows that \(y-x-1\geq 0\). Also, because \(2z\leq q-p+1\) and \(q-p\geq 3\), it follows that \((y-x-1)\leq 0\). Therefore \(x=y-1\) and, consequently, \(z=(q-p-1)/2\).

\[lem3245\] If \(B\) is a \((p,q)\)-\(B\)-type multigraph and \(B'=B'(A,\cA,v'v,'')\) then \(d(B',u)=d(B,u)+2(1-d(A,u))\) for all \(u\in Q\).

By definition \(E(B')=E(B)\backslash E(A)\cup E_{v'}\cup E_{v'}\). Therefore \(d(B',u)=d(B,u)-d(A,u)+(1-d(A_1,u))+(1-d(A_2,u))\). Now, as \(d(A_1,u)+d(A_2,u)=d(A,u)\) it follows that \(d(B',u)=d(B,u)+2(1-d(A,u))\).

\[lem3250\] Suppose that \(p\geq q+7\), \(\cB\) is a Ryser proper-type decomposition of a \((p,q)\)-\(B\)-type multigraph \(B\), \(A\in\cB\) and \((A,\cA)\) is a provisional suitably decomposed Ryser \(v\)-proper subgraph of \(B\) such that \(S(A,\cA,v',v'')\) is \((q-p+1)\)-bad. Then for both \(\Lambda\in\{S,T\}\), \(V(\Lambda)\cap Q\) contains vertices \(u_1=u_1(\Lambda)\) and \(u_2=u_2(\Lambda)\) with the property that, for some \(A'\in\cB\backslash \{A,A''\}\), where \(A''\in\cB\) denotes the subgraph containing the unique loop of \(T\), both \(d(B,u_1)\leq q-p-5+2d(A',u_1)\) and \(d(A',u_2)\leq 1\) hold. Moreover, if \(u_1\neq u_2\) then, for some \(A'''\in\cB\backslash\{A,A'\}\) the subgraph \(A'''\) has a path component with ends \(u_1\) and \(u_2\).

First the lemma is proved for \(\Lambda=T\). As \(S\) is \((q-p-1)\)-bad it follows from Lemma \[lem3240\] that \(|V(S)\cap P|=|V(S)\cap Q|-1\). Therefore, as \(p\geq q+7\), it follows that \(|V(T)\cap P|=|V(T)\cap Q|-5\). Consequently, \(V(T)\cap Q\) contains at least one vertex \(u\) which satisfies \(d(T,u^{\star})\leq q-p-3\).

As \(|B\backslash\{A,A''\}|=(q-p+1)=(q-p+1)/2-2=(q-p-3)/2\) it follows that if \(d(T,u)\leq q-p-5\) then there exists \(A'\in\cB\backslash\{A,A''\}\) such that \(d(A',u)\leq 1\). Now, if \(u^{\star}\in V(T)\cap Q\) satisfies \(d(T,u^{\star})\leq q-p-7\) let \(A'\in\cB\backslash\{A,A''\}\) be such that \(d(A',u)\leq 1\). In this case \(u_1(T)=u_2(T)=u^{\star}\) and \(A'\) suffice because \(d(B,u^{\star})=d(T,u^{\star})+2\leq q-p-5\leq q-p-5+2d(A',u^{\star})\).

If \(u^{\star}\in V(T)\cap Q\) satisfies \(d(T,u^{\star})=q-p-5\) and also satisfies \(d(A',u^{\star})=1\) for some \(A'\in\cB\backslash\{A,A''\}\) then, again \(u_1(T)=u_2(T)=u^{\star}\) and \(A'\) suffice because \(d(B,u^{\star})=d(T,u^{\star})+2=q-p-3=q-p-5+2d(A',u^{\star})\).

Now suppose every vertex \(u\in V(T)\cap Q\) satisfies \(d(T,u)> q-p-7\) and every \(v\in V(T)\cap Q\) which satisfies \(d(T,u)=q-p-5\) also satisfies \(d(D,u)\neq 1\) for all \(D\in\cB\backslash\{A,A''\}\).

Let \(X=\{u\in V(T)\cap Q\,|\,d(T,u)=q-p-3\}\) and let \(Y=\{u\in V(T)\cap Q\,|\, d(T,u)=q-p-5\}\). As \(d(T,u)=q-p-1\) for all \(u\in V(T)\cap P\), every edge of \(T\) has either an end in \(P\) or is a loop with its end in \(Q\), and \(T\), by Lemma \[lem3240\] has exactly one loop it follows that \(2|E(T)|=p_T(q-p-1)+2\), where \(p_T=|V(T)\cap P|\). Also, as every edge of \(T\) has an end in \(Q\) and every vertex in \(V(T)\cap Q\) is, by assumption, either a vertex in \(X\) or a vertex in \(Y\) it follows that \(2|E(T)|=2x+4y\), where \(x=|X|\) and \(y=|Y|\). Therefore \(p_T(q-p-1)+2=2x+4y\). Now, by Lemma \[lem3240\], \(p_T=q-p-3\). Therefore \(2x=(q-p-3)(q-p-1)-(4y-2)\) and, because \(p\equiv (q-1)\bmod{2}\), it follows that \(x\) is odd.

Let \(X_1=\{u\in X\,|\, d(A,u)=1\}\) and let \(X_2=\{u\in X\,|\,d(A,u)=2\}\). As \(X_1\) is the set of all end-vertices of path components of \(A\) with both end-vertices in \(V(T)\) it follows that \(|X_1|\) is even. Therefore, as \(x=|X_1|+|X_2|\) is odd \(|X_2|\) is also odd.

For every pair \(\{D,D'\}\subset\cB\) let \[X_2(D,D')=\{u\in X_2\,|\, d(D,u)-d(D',u)=1\}.\] Then, because \(d(A,u)=d(A'',u)=2\) for all \(u\in X_2\) it follows that \[\bigcup_{\begin{scriptsize}\begin{array}{c}\{D,D'\}\subseteq\cB\backslash\{A,A''\} \\ D\neq D'\end{array}\end{scriptsize}}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!X_2(D,D')=X_2\]

Now, as \(|X_2|\) is odd there exists at least one pair \(\{D_1,D_2\}\subseteq\cB\backslash\{A,A'\}\) such that \(|X_2(D_1,D_2)|\) is odd.

As \(|X_2(D_1,D_2)|\) is odd it follows that there is a path component in \(D_1\) with end-vertices \(v_1\in X(D_1,D_2)\) and \(v_2\in X_2(D_1,D_3)\) where \(D_3\in\cB\backslash\{A,A'',D_1\}\). Let \(u_1(T)=v_1\), \(u_2(T)=v_2\), \(A'=D_3\) and \(A'''=D_1\). Then \(d(B,v_1)=q-p-3+2=q-p-1=q-p-5+2d(D_3,v_1)\), \(d(D_3,v_2)=1\) and \(D_1\) has a path component with end-vertices \(v_1\) and \(v_2\).

So the lemma holds for \(\Lambda=T\). Now the \(\Lambda=S\) case is proved.

As \(S\) is \((q-p-1)\)-bad it follows, by definition, that there exists \(u^{\star}\in V(S)\cap Q\) such that \(d(S,u^{\star})=q-p-3\) and \(d(S,u)=q-p-1\) for all \(u\in (V(S)\cap Q)\backslash\{u^{\star}\}\). As \(A\) is \(v\)-Ryser for some \(v\in Q\) it follows from Lemma \[lem2630\] that \(d(A,u^{\star})\leq 2\).

If \(d(A,u^{\star})=0\) then, by Lemma \[lem3245\], \(d(B,u^{\star})=q-p-5\). As \(\cB\backslash\{A,A''\}=(q-p-3)/2\) it follows that there exists some \(A'\in\cB\backslash\{A,A''\}\) such that \(d(A',u^{\star})\leq 1\). In this case \(u_1(S)=u_2(S)=u^{\star}\) and \(A'\) suffice because \(d(B,u^{\star})=q-p-5\leq q-p-5+2d(A',u^{\star})\) and \(d(A',u^{\star})\leq 1\).

Before proving the remaining cases, namely \(d(A,u^{\star})=1\) and \(d(A,u^{\star})=2\) it is shown that if there exists some \(A'\in\cB\backslash\{A,A''\}\) such that \(d(A',u^{\star})\leq 1\) and there exists some \(A'''\in\cB\backslash\{A,A'\}\) such that \(d(A''',u^{\star})=1\) then the lemma holds.

Suppose then that there exists some \(A'\in\cB\backslash\{A,A''\}\) such that \(d(A',u^{\star})\leq 1\) and there exists some \(A'''\in\cB\backslash\{A,A'\}\) such that \(d(A''',u^{\star})=1\). As \(d(A''',u^{\star})=1\) it follows that \(A'''\) has a path component with ends \(u^{\star}\) and \(w\in V(S)\cap Q\). As \(S\) is \((q-p-1)\) and \(w\neq u^{\star}\) it follows that \(d(S,w)=q-p-1\). Moreover, because \(d(A''',w)=1\) it follows that \(d(B,w)= q-p-1\). Also, by Lemma \[lem3245\], it follows that \(d(B,w)\geq q-p-3\). Therefore as \(d(B,w)\equiv (q-p-1)\bmod{2}\) it follows that \(d(B,w)\in\{q-p-1,q-p-3\}\).

If \(d(B,w)=q-p-1\) then, as \(|\cB\backslash\{A,A'''\}|=(q-p-3)/2\) and \(d(A,w)=d(A''',w)=1\) it follows that \(d(D,w)=2\) for all \(D\in\cB\backslash\{A,A'''\}\). In particular \(d(A',w)=2\). In this case, if \(u_1(S)=w\) and \(u_2(S)=u^{\star}\) then \(d(B,w)=q-p-1=q-p-5+2d(A',w)\) and \(d(A',u^{\star})\leq 1\). The lemma holds because \(A'''\) has a path component with end-vertices \(u^{\star}\) and \(w\).

If \(d(B,w)=q-p-3\) then \(d(A,w)=0\) and therefore as \(|\cB\backslash\{A,A''\}|=(q-p-3)/2\) and \(d(A''',w)=1\) it follows that \(d(P,w)\geq 1\) for all \(D\in\cB\backslash\{A,A'''\}\), in particular \(d(A',w)\geq 1\). If \(d(A',w)=1\) then \(u_1(S)=u_2(S)=w\) satisfy the lemma because \(d(B,w)=q-p-3=q-p-5+2d(A',w)\). If \(d(A',w)=2\) then \(d(B,u^{\star})=q-p-1=q-p-5+2d(A',w)\), \(d(A',u^{\star})\leq 1\) and \(A'''\) has a path component with end-vertices \(u^{\star}\) and \(w\).

So the lemma holds for \(\Gamma=S\) if there exists some \(A'\in\cB\backslash\{A,A''\}\) such that \(d(A',u^{\star})\leq 1\) and there exists some \(A'''\in\cB\backslash\{A,A'\}\) such that \(d(A''',u^{\star})=1\).

Now, if \(d(A,u^{\star})=1\) then, by Lemma \[lem3245\], \(d(B,u^{\star})=q-p-3\) and so, as \(d(D,u^{\star})\leq 2\) for all \(D\in\cB\) it follows that either (i) there exists a subset \(\{A_1,A_2,A_3\}\subseteq\cB\backslash\{A\}\) such that \(d(A_i,u^{\star})=1\) for all \(i\in [3]\) and \(d(A_i,u^{\star})=2\) for all \(A_i\in\cB\backslash\{A,A_1,A_2,A_3\}\) or (ii) there exists a subset \(\{A_1,A_2\}\subseteq\cB\backslash\{A\}\) such that \(d(A,u^{\star})=1\) and \(d(A_2,u^{\star})=0\).

If (i) holds then let \(A'\in\{A_1,A_2,A_3\}\backslash\{A''\}\). If (ii) holds and \(A_1=A''\) then let \(A'=A_1\). In both cases \(d(B,u^{\star})=q-p-3=q-p-5+2d(A',u^{\star})\) and \(d(A',u^{\star})=1\) and therefore \(u_1(S)=u_2(S)=u^{\star}\) satisfy the lemma. Otherwise, if (ii) holds then \(A_1=A''\) in which case, if \(A'=A_2\) then \(d(A',u^{\star})=0\leq 1\) and \(A'''=A_1\in\cB\backslash\{A,A''\}\) satisfies \(d(A''',u^{\star})=1\). So the lemma holds because there exists some \(A'\in\cB\backslash\{A,A''\}\) such that \(d(A',u^{\star})\leq 1\) and there exists some \(A'''\in\cB\backslash\{A,A'\}\) such that \(d(A''',u^{\star})=1\).

Finally, if \(d(A,u^{\star})=2\) then, by Lemma \[lem3245\], \(d(B,u^{\star})=q-p-1\). As \(\cB\) is Ryser it follows, for some \(\{A_1,A_2\}\subseteq\cB\backslash\{A\}\), that \(d(A_1,u^{\star})=d(A_2,u^{\star})=1\). Here let \(A'\in\{A_1,A_2\}\backslash\{A''\}\) and \(A'''\in\{A_1,A_2\}\backslash\{A'\}\). Then \(d(A',u^{\star})=1\) and \(d(A''',u^{\star})=1\). Again the lemma holds because there exists some \(A'\in\cB\backslash\{A,A''\}\) such that \(d(A',u^{\star})\leq 1\) and there exists some \(A'''\in\cB\backslash\{A,A'\}\) such that \(d(A''',u^{\star})=1\).

\[lem3254\] If \(p=q+5\), \(\cB\) is a Ryser proper-type decomposition of a \((p,q)\)-\(B\)-type multigraph \(B\), \(A\in\cB\) and \((A,\cA)\) is a provisional suitably decomposed Ryser \(v\)-proper-type subgraph of \(B\) then \(S(A,\cA,v',v'')\) is \((q-p-1)\)-good.

Suppose \(S=S(A,\cA,v',v'')\) is \((q-p-1)\)-bad. By Lemma \[lem3240\] \(E(S)\) contains exactly one loop and, because \((q-p-3)/2=1\), \(E(T)\), where \(T=T(A,\cA,v',v'')\), also contains exactly one loop. Let \(\lambda\) be the unique loop in \(E(T)\). Without loss of generality suppose that \(v_1\) is the end of \(\lambda\) and \(A'\) is the Ryser \(v_1\)-proper-type subgraph of \(B\) containing \(\lambda\).

As \(B'\) is \((p+2,q)\)-\(B\)-type it follows by definition that \(\Delta(T)=q-p-1=4\) and \(p\equiv q-1\bmod{2}\). Therefore as \(v_1\) is the end of a loop, and hence \(d(T,v_1)\geq 2\), it follows that \(d(T,v_1)\in\{2,4\}\). If \(d(T,v_1)=2\) then, because \(d(A,v_1)=2\), it follows, by Lemma \[lem3245\], that \(d(B,v_1)=4\). Now, as \(d(A,v_1)=d(A',v_1)=2\) it follows that \(d(A'',v_1)=0\) where \(A''\in\cB\backslash\{A,A'\}\). Therefore \(\cB\) is not Ryser, a contradiction. Hence \(d(T,v_1)=4\) and, consequently, \(d(B,v_1)=6\) and \(d(A,v_1)=d(A',v_1)=d(A'',v_1)=2\).

If \(v_i\in V(T)\cap C\) and \(v_i\neq v_1\) satisfies \(d(T,v_i)=4\) then, because \(d(B,v_i)=6\), \(\lambda\) is the only loop of \(T\) and \(\cB\) is Ryser, it follows that \(d(A,v_i)=d(A',v_i)=d(A'',v_i)=2\). Similarly, if \(d(T,v_i)=2\) then \(d(B,v_i)=4\) and, because \(\cB\) is Ryser, \(d(A,v_i)=2\) and \(d(A',v_i)=d(A'',v_i)=1\).

If \(X=\{v_i\in V(T)\cap C\,|\, d(B,v_i)=4\}\) and \(Y=\{v_i\in V(T)\cap C\,|\,d(B,v_i)=2\}\) then there are \(|Y|+2(|X|-1)\) non-loop edges of \(A'\) in \(E(T)\) and \(|Y|+2|X|\) non-loop edges of \(A''\). This is a contradiction because \(E(T)\) contains exactly \(2|V(T)\cap V|\) edges in common with both \(A'\) and \(A''\). Hence \(S\) is \((q-p-1)\)-good.

\[lem3256\] Suppose that \(p\geq q+7\), \(\cB\) is a Ryser proper-type decomposition of a \((p,q)\)-\(B\)-type multigraph \(B\), \(A\in\cB\) and \((A,\cA)\) is a provisional suitably decomposed Ryser \(v\)-proper subgraph of \(B\) such that \(S(A,\cA,v',v'')\) is \((q-p-1)\)-bad. Then there is a Ryser proper-type decomposition \(\cB'\) of \(B\) and a \(v\)-proper-type subgraph \(A'\in\cB'\) such that, for some provisional decomposition \(\cA\), \(S(A,\cA,v',v'')\) is \((q-p+1)\)-good.

As \(S=S(A,\cA,v',v'')\) is \((q-p-1)\)-bad it follows, from Lemma \[lem3250\], that, for \(\Lambda\in\{T,S\}\), there exist vertices \(u_1=u_1(\Lambda)\in V(\Lambda)\cap P\) and \(u_2=u_2(\Lambda)\in V(\Lambda)\cap Q\) such that, for some \(A'=A'(\Lambda)\in\cB\backslash\{A,A''\}\) (where \(A''\) is the unique Ryser proper subgraph in \(\cB\) containing the unique loop of \(T\)) \(d(B,u_1)\leq q-p-5+2d(A',u_1)\) and \(d(A',u_2)\leq 1\) hold. Moreover, if \(u_1\neq u_2\) then, for some \(A'''=A'''(\Lambda)\in\cB\backslash\{A,A'(\Lambda)\}\) the subgraph \(A'''\) has a path component with end-vertices \(u_1\) and \(u_2\).

Let \(A_1'=A'(T)\) and \(A_2'=A'(S)\). If \(A_1'=A_2'\) then let \(\cB'=\cB\). Otherwise let \(\cB'=(\cB\backslash\{A_1',A_2'\})\cup A_1''\cup A_2''\) where \(A_1''=(V(B),E(A_1''))\), \(A_2''=(V(B),E(A_2''))\) and \(E(A_1'')\) and \(E(A_2'')\) are given by \[E(A_1'')=(E(A_1')\cap E(T))\cup (E(A_2')\cap E(S))\] \[E(A_2'')=(E(A_2')\cap E(T))\cup (E(A_1')\cap E(S))\]

\(\cB'\) is a Ryser proper-type decomposition of \(B\). If \(\cB'=\cB\) this is obvious because \(\cB\) is a Ryser proper-type decomposition of \(B\). Otherwise \(\cB'=(\cB\backslash\{A_1',A_2'\})\cup A_1''\cup A_2''\) andd \(\cB'\) is a Ryser proper-type decomposition if and only if \(A_1''\) and \(A_2''\) are both Ryser \(v\)-proper-type subgraphs of \(B\) for some \(v=v(i)\in Q\).

By definition \(E(A_1'')=(E(A_1')\cap E(T))\cup (E(A_2')\cap E(S))\). Therefore, as \(A_1'\) and \(A_2'\) are both proper-type subgraphs of \(B\) and no edge in \(E(T)\) has an end in common with an edge in \(E(S)\) it follows that \(\Delta(A_1'')=2\) and \(d(A_1'',u)=2\) for all \(u\in P\). By similar reasoning it follows that \(\Delta(A_2'')=2\) and \(d(A_2'',u)=2\) for all \(u\in P\).

For \(i\in\{1,2\}\) the edge-set \(E(A_i'')\) contains exactly one loop because \(E(A_i'')\) contains exactly one loop and because \(E(T)\) contains exactly one loop \(\lambda\) and \(\lambda\in E(A'')\) and \(A_1''\neq A''\) and \(A_2''\neq A''\). Therefore \(|E(A_1'')|=|E(A_2'')|=2p+1\) and \((vv,1)\in E(A_i''')\) for some \(v=v(i)\in Q\).

Finally, because \(\cB\) is Ryser, \(d(B,u)=q-p+1\) implies \(d(A,u)=2\) for all \(u\in Q\) and \(A\in\cB\). Therefore \(d(B,u)=q-p+1\) implies \(d(A_i'',u)=2\) for all \(u\in\cB\) and \(i\in\{1,2\}\). Also, because \(\cB\) is Ryser, \(d(B,u)=q-p-1\) implies \(d(A,u)\geq 1\) for all \(u\in Q\) and \(A\in\cB\). Therefore \(d(B,u)=q-p-1\) implies \(d(A_i'',u)\geq 1\) for all \(u\in\cB\) and \(i\in\{1,2\}\).

Now it follows that \(A_i''\) is Ryser \(v\)-proper-type for some \(v=v(i)\), where \(i\in\{1,2\}\). Hence \(\cB'\) is a Ryser proper-type decomposition of \(\cB\). Therefore, as \(A_1''\in\cB'\) it follows that \(A_1''\) is a Ryser \(v\)-proper-type subgraph of \(B\), for some \(v\in Q\). By Lemma \[lemXXXX\] there is a provisionall suitable decomposition \(\cA''\) of \(A_1''\). Let \(B''=B'(A_1'',\cA'',v,v'')\).

Let \(\Lambda\in\{S,T\}\). Then, because \(d(B,u_1(\Lambda))\leq q-p-5+2d(A'(\Lambda),u_1(\Lambda))\), it follows that \(d(B,u_1(\Lambda))\leq q-p-5+2d(A_1'',u_1(\Lambda))\) and, because \(d(A'(\Lambda),u_2(\Lambda))\leq 1\) it follows that \(d(A_1'',u_2(\Lambda))\leq 1\). Moreover, as \(A'''(\Lambda)\in\cB\backslash\{A_1'\}\) it follows that \(A'''(\Lambda)\) is a subgraph of \(B''\). Therefore, as \(A'''(\Lambda)\) has a path component with ends \(u_1(\Lambda)\) and \(u_2(\Lambda)\) it follows that \(u_1(\Lambda)\) and \(u_2(\Lambda)\) are vertices of the same component of \(B''\). Now, as \(d(A_1'',u_2(\Lambda))\leq 1\) it follows, by definition, that either \(v'u_2(\Lambda)\in E(B'')\) or \(v''u_2(\Lambda)\in E(B'')\). Therefore, \(\{u_2(S),u_2(T)\}\subseteq V(S'')\) and hence \(\{u_1(S),u_1(T)\}\subseteq V(S'')\). As \(u_1(S)\neq u_1(T)\) and \(d(B'',u_1(\Lambda))\leq q-p-3\) for both \(\Lambda\in\{S,T\}\) it follows that \(S''\) is \((q-p-1)\)-good.

Results \[sec3260\]

\[thm3270\] A proper \(C\)-edge-coloured \(r\)-free-type simple graph \(\cH\) of even order \(n\) can be embedded in some proper \(C\)-edge-coloured complete simple graph of order \(n\) if and only if \(\cH\) is Ryser and \((n-r)\)-good.

The necessity of \(\cH\) being Ryser follows from Lemma \[lem2020\] while the necessity of \(\cH\) being \((n-r)\)-good follows from Corollary \[cor3070\].

Suppose now that \(\cH\) is Ryser and \((n-r)\)-good. As \(n\) is even and \(\cH\) is an \(r\)-free-type simple graph of order \(n\) it follows that \(r\leq n\) is also even. Therefore \(n-r\in\{0,2,4,6,\ldots\}\)

If \(n-r=0\) then, by definition, \(\cH\) is a proper \(C\)-edge-coloured complete simple graph of order \(n\) in which \(\cH\) is embedded. If \(n-r=2\) then, by Corollary \[cor3075\], \(\cH\) has a Ryser \(\eps\)-extension \(\cJ\) for every \(\eps\in F\). Let \((\eps,\cJ)\) be a Ryser edge-extension of \(\cH\). Then \(n-r(\cJ)=n-r-2=0\) and so \(\cJ\) is a proper \(C\)-edge-coloured complete simple graph of order \(n\) in which \(\cH\) is embedded.

Suppose now that \(n-r\geq 4\) and every Ryser \((n-r')\)-good proper \(r'\)-free-type simple graph of order \(n\), with \((n-r')/2<2\), can be embedded in a proper \(C\)-edge-coloured complete simple graph of order \(n\).

By Corollary \[cor3070\] it follows that \(\BH\) has a Ryser proper decomposition \(\cB\). Let \(\eps\in F\) and let \(A\in\cB\) be a Ryser \(\phi(\eps)\)-proper graph. By Lemma \[lem2800\] \(A\) has a provisional suitable decomposition \(\cA\). Let \(\cJ\) be the provisional Ryser \(\eps\)-extension of \(\cH\) corresponding to the provisional suitably decomposed Ryser \(\phi(\eps)\)-proper graph \((A,\cA)\).

If \(n-r=4\) then \(n-r(\cJ)=2\) and so, by definition, \(\cJ\) is \((n-r-2)\)-good. Therefore, by induction, \(\cJ\) can be embedded in a proper \(C\)-edge-coloured complete simple graph \(\cK\) of order \(n\). Hence, \(\cH\) can be embedded in in a proper \(C\)-edge-coloured complete simple graph of order \(n\).

Suppose now that \(n-r\geq 6\). By Lemma \[lem3110\] \(\BH\) is \((r,n-1)\)-\(B\)-type and by Lemma \[lem3170\] \(\BJ=B(A,\cA,v_{r+2}v_{r+2})\) and by Lemma \[lem3110\] \(\BJ\) is \((r+2,n-1)\)-\(B\)-type. Therefore, by Lemma \[lem3230\], every component of \(T(\cJ)\) is \((n-r-2)\)-good. Now, if \(S(\cJ)\) is \((n-r-2)\)-good it follows that every component of \(\BJ\) is \((n-r-2)\)-good. Therefore, by Lemma \[lem3060\], \(\cJ\) is \((n-r-2)\)-good and, by induction, \(\cH\) can be embedded in a proper \(C\)-edge-coloured complete simple graph of order \(n\).

If \(n-r=6\) then, by Lemma \[lem3254\], \(S(\cJ)\) is \((n-r-2)\)-good. Therefore \(\cH\) can be embedded in a proper \(C\)-edge-coloured complete simple graph of order \(n\).

If \(n-r\geq 8\) and \(S(\cJ)\) is \((n-r-2)\)-bad then, by Lemma \[lem3256\], there is a Ryser proper decomposition \(\cB'\) of \(\BH\) with the property that, for some provisional decomposition \(\cA'\) of some Ryser proper subgraph \(A'\in\cB'\) \(S(A',\cA'',v_{r+1},v_{r+2})\) is \((n-r-2)\)-good. Now, because Lemma \[lem3230\] implies that every component of \(T(\cJ')\) is \((n-r-2)\)-good it follows that every component of \(B(\cJ')\) is \((n-r-2)\)-good and therefore, by Lemma \[lem3060\], \(\cJ'\) is \((n-r-2)\)-good. Therefore, by induction, \(\cH\) can be embedded in a proper \(C\)-edge-coloured complete simple graph of order \(n\).