1
$\begingroup$

I want to prove that every graph $G$ embeddable in the projective plane has a vertex of degree $\leq 5$. If I suppose the graph has a $2-$cell embedding (an embedding in a way every face is homeomorphic to a disk) we can extend it to a triangulation and in a triangulation we can easily prove using Euler's formula that there are exactly $3n-3$ edges, from which we get that $\delta(G)\leq 2\frac{3n-3}{n}<6$ so we get the result.

In the general case, when the embedding is arbitrary, I wanted to approach it proving that every graph which can be embedded in the projective plane, can be seen as a subgraph of a graph with a $2-$cell embedding. I don't know if this is true, but at the least, if the graph is planar, we can add edges to make it into a maximal planar graph, so that the outer face (in a plane embedding) is a triangle, and drawing it inside the cycle $4564$ in the following $2-$cell embedding of $K_{6}$ (edges of the same color are identified) would make it a subgraph of a $2-$cell embeddable graph.

enter image description here

I think the same approach would work to prove that planar graphs can be drawn as subgraphs of $2-$cell embeddable graphs in any compact and closed surface.

But what happens if the graph is not planar? Is there a better approach for this?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.