Define two operations:

B-operation: When two multi-edges connect a pair of vertices, replace the multi-edges with a single edge connecting the pair of vertices.

C-operation: When one edge connects vertices $u$ and $v$, another edge connects $v$ and $w$ (where $u \ne w$), and there is no other edge incident to $v$, remove the vertex $v$, and replace the two edges with a new edge connecting $u$ and $w$.

How to prove a non-planar graph can't become a graph with only two vertices and a single edge by repeating B and C?

Two examples:

  • $K_3$, let the vertices be called $A_1,A_2,A_3$. Use C on $A_2$ to remove $A_2$, then B on $A_1$ and $A_3$ to remove the redundant edge.

  • $K_4$, since all vertex degrees are 3, no C is possible, and since there are no multi-edges, no B is possible.


1 Answer 1


Show that if $G$ reduces to $H$ via one of your operations and $H$ is planar, then $G$ is also planar.

  • $\begingroup$ So it means B and C operation has closure on planar. And also their reverse action. $\endgroup$ Commented Apr 17, 2022 at 17:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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