1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Got it! Thank you so much! Rarely use subdivision to count~~ $\endgroup$ – Andy Feb 25 '19 at 11:31
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Got it! Thank you so much. You gave a very detailed description. $\endgroup$ – Andy Feb 25 '19 at 11:35

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.