In 1990, Bondy posed the small circuit double cover (SCDC) conjecture: Every 2-connected graph has a circuit double cover (CDC) with the number of circuits less than |V| (the order of the vertex set V). The strong embedding conjecture states that every 2-connected graph has a strong embedding on some surface in which the boundary of each face is a circuit. In this paper, HP-graph is defined as the graph which has a strong embedding on the projective plane with one face of valence |V| and the other faces of valence 3. And it is proved that the HP-graph has a strong embedding with |V| - 1 or less faces on some surface, which confirms both the SCDC conjecture and the strong embedding conjecture.
展开▼
