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?


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.