Three-regular subgraphs of four-regular graphs (Q5906272)

It is known that any simple 4-regular graph contains a 3-regular subgraph. In the present paper the authors consider finite undirected graphs with multiple edges but without loops. They extend the above given result to such 4-regular graphs \(G\). They use the concept of Euler orientation defined as follows: Let \(G= (V,E)\) be a 4-regular graph with \(v_i\in V\), \(| V|= n\), \(| E|= 2n\). Then an Euler orientation of \(G\) is a partition \(E= \bigcup^n_{i= 1} A_{v_i}\) of the set \(E\) of edges such that \(A_{v_i}\) and \(A_{v_j}\) are disjoint for any \(i\neq j\) and each \(A_{v_i}\) has exactly two edges both incident with \(v_i\). \(N= N(G)\) denote the number of Euler orientations of \(G\). The main result of the paper is Theorem 2.2: A 4-regular graph \(G\) with \(n\) vertices has a 3-regular subgraph if \(N\not\equiv 1\pmod 3\). This theorem is extended to Theorem 2.3: A \(2m\)-regular graph \(G\) has a \(p\)-regular subgraph (\(p\) a prime such that \(p- 1\leq m\)) if \(N\not\equiv 1\pmod p\). Further a set of 4-regular graphs with multiple edges is given which have no 3-regular subgraphs but for which the authors know exactly the number \(N\) of Euler orientations. Finally a conjecture of Thomassen is reduced to 4-regular graphs only with multiple edges. It asserts that any 4-regular connected graph with an even number of vertices has a 3-regular subgraph. This has been proved by the second author.