The estimation of Eulerian OE-cover cardinality for a plane graph

Abstract

The article considers the estimates for the number of chains of Eulerian OE-cover for a plane graph by chains. The Eulerian OE-cover is such a minimal cardinality ordered set of edge-disjoint chains for which the condition that there is no intersection of the interior of the cycle from the edges of the traversed part of the route with the edges of the unpassed part is satisfied. In accordance with the Listing-Luke theorem, the minimal cardinality of a cover by edge-disjoint chains is equal to k, where 2k is the number of odd degree vertices. Earlier, the author showed that the cardinality of Eulerian OE-cover of a plane graph without bridges is equal to k if at least one vertex of odd degree is incident on the outer face and k + 1, otherwise. In this paper I show that the exact upper bound for the cardinality of the Eulerian OE-cover is equal to 2k.