COVERING THE EDGES OF A GRAPH BY FOUR ODD SUBGRAPHS

Abstract

A graph is odd if all its vertices have odd degrees. A Shannon triangle is a loopless graph on three pairwise adjacent vertices. If the parities of the sizes of its bouquets (of parallel edges) are denoted by \(p,q,r\) in non-increasing order, with \(2\) (resp. \(1\)) denoting an even-sized (resp. odd-sized) bouquet, we then say the Shannon triangle is of type \((p,q,r)\). The minimum number of odd subgraphs which cover its edges is \(p+q+r\). For a Shannon triangle of type \((2,2,2)\) (resp. \((2,2,1)\)) this number equals \(6\) (resp. \(5\)). We prove that, by excluding these two types of Shannon triangles, every other loopless connected graph admits an edge cover by four odd subgraphs.