Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
Consider a connected undirected simple non-planar graph $G$ with $15$ vertices. If removing any edge from $G$ results in a planar graph, how many edges does $G$ have?
It is obvious that if the number of edges greater than $3*15-6=39$, then it is not planar. But, how to discuss "removing any edge make it planar"? Thanks
The number of edges of $G$ is either $18$ or $20$.
Since graph $G$ is non-planar, by Kuratowski's theorem, it contains a subdivision of either $K_5$ (the complete graph of $5$ vertices) or $K_{3,3}$ (the complete bipartite graph of $6$ vertices) as a subgraph.
Since removing any edge from $G$ make it planar, above subgraph exhaust all edges of $G$. This means $G$ is a subdivision of either $K_5$ or $K_{3,3}$.
Notice subdividing a graph increases the number of vertices and edges by same amount.
If we start from $K_5$ which has $5$ vertices and $10$ edges, we need to subdivide $10$ times to get $15$ vertices. In this case, the resulting graph will have $10 + 10 = 20$ edges.
If we start from $K_{3,3}$ which has $6$ vertices and $9$ edges, we need to subdivide $9$ times to get $15$ vertices. In that case, the resulting graph will have $9+9 = 18$ edges.
I am not sure if this is the answer you are looking for, but a discussion on this topic can conclude upper and lower bounds for the number of edges in such a graph.
As you have already stated, we can determine the upper limit using the Euler characteristic, $ v-e+f-c=1 $ which we can reduce to $v-e+f=2$ since our graph is connected. Because we know that our original graph $G$ is non-planar before removing an edge, we can say that $\left|E\right|=e+1$. We can use the maximum possible faces of a planer graph with $v=15$ to find $e$ using $f_{max}=2v-4 = 26$ $$ 15-e+26=2 \implies \left|E\right| \leq 40 \leftarrow\textrm{upper bound} $$
To find the lower bound, we can use Kuratowski's Theorem (see here for a nice explanation) to state a lower bound, $\left|E\right| \geq v+3 = 18$.
So, we can say that for a non-planar graph $G$, with $\left|V\right|=15$ and the property that removing an edge must make the result planar, has $ 18\leq\left|E\right|\leq 40 $ edges.
Essentially, if the number of edges is less than the lower bound, we know that the graph must be planar. If the number of edges is greater than the upper bound, we would have to remove more than one edge to make it planar.
