Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

By Kuratowski's Theorem,

A graph is planar if and only if it does not contain a subgraph isomorphic to a subdivision of K5 or K(3,3).

My question is that for the subdivision of K5 (or K(3,3) formed by adding vertices to K5 or K(3,3), must those vertices be distinct?

Thanks a lot.

share|cite|improve this question
Distinct from what? – Gerry Myerson Apr 2 '12 at 1:14
Just to clarify, I meant whether the added vertices must be distinct. As in, is it possible to add the vertex $v_1$ twice. – yoyostein Apr 2 '12 at 4:17
I drew a rough picture here: ( Perhaps I should rephrase the question -- can the added vertex ($v_7$) be incident to more than one edges (in this case $v_1v_6$, $v_2v_5$, $v_3v_4$)? Thanks a lot once again. – yoyostein Apr 2 '12 at 4:24
That 7-vertex graph is planar. You can draw it as a cycle $v_1-v_5-v_3-v_6-v_2-v_4-v_1$ with $v_7$ in the middle joined to the other 6. So in the sense in which you are using the term, yes, the vertices must be distinct. – Gerry Myerson Apr 2 '12 at 4:51
up vote 1 down vote accepted

OP has clarified used the comments to clarify the question. If you have drawn a graph $G$ in the plane in such a way that two (or more) edges cross at a point $v$, then adding $v$ to $G$ as a vertex does not qualify as making a subdivision of $G$. Otherwise, you could take any graph, planar or otherwise, and put down new vertices at all the crossing points, and you'd have a planar graph, so nonplanar graphs would have planar subdivisions, and the concept of subdivision would be irrelevant to planarity.

Perhaps more precisely; a subdivision of a graph is a graph homeomorphic to the original, and you don't get that when you put down new vertices at crossing points.

share|cite|improve this answer

I'm having trouble understanding an aspect of this question. When I think of a graph, I think of a set of vertices and a set of edges between different vertices. So if, in $K_{3,3}$, I split an edge into two edges by adding a vertex $v_0$ into the 'middle' of the edge and view the new graph as having one additional vertex and one additional edge, that's okay.

But I think you want to add the same vertex again. What does that mean? It seems there are two interpretations: either we literally claim for a moment that our vertex $v_0$ is now also some vertex $v_1$, then we have changed nothing. We have added no edges, we have changed no connectivity, and our new vertex set hasn't really changed.

The other interpretation is to copy the vertex and its connections, and add the copy. Let me give an example to say what I mean. We might start with two points and an edge between them. We add the midpoint, so we have a 2-segment straight line. If we add a 'copy' of the midpoint and its edges, then we get a diamond.

In both cases, if they are called 'subdivisions' (and I would not call the first interpretation a subdivision, but instead the exact same graph), they preserve non-planarity.

All this is to say that no, the vertices don't have to be distinct, but they might as well be.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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