Circuit Decompositions and Shortest Circuit Coverings of Hypergraphs

It is one of fundamental theorems in graph theory that every even graph has a circuit decomposition. This classical result for ordinary graphs is extended in this paper for uniform bridgeless hypergraphs if the degree of every vertex is even. One of major open problems for shortest circuit cover was a conjecture proposed by Itai and Rodeh (Automata, Languages and Programming, Lecture Notes in Computer Science, vol. 62, pp. 289–299. Springer, Berlin, 1978) that every bridgeless graph G has a circuit cover of total length at most $$|E|+|V|-1$$ . This conjecture was solved by Fan (J Combin Theory Ser B 74:353–367, 1998) for ordinary graphs, and is extended in this paper for bridgeless hypergraphs.