4
$\begingroup$

So I've recently read the infinite graph version of Kuratowski's theorem. It says that a graph $G$ is planar if and only if the following three conditions holds:

  1. $|V(G)| \le |\mathbb{R}|$
  2. $G$ has at most countably many vertex with degree at least 3
  3. $G$ has neither $K_{3,3}$ nor $K_5$ subdivision

It is clear that if a graph $G$ is planar, then all three conditions must hold. To show its converse, I assume that there is a graph that satisfies all three condition and yet it is not planar. I have eliminated condition 1 and 3 as a source of non-planarity of $G$, but I cannot derive a contradiction with 2. Any help would be greatly appreciated.

$\endgroup$
4
$\begingroup$

I am not sure which direction gives you trouble, but the second condition is necessary, by the Moore-Young theorem, or a somewhat weaker version thereof, as discussed by Greg Kuperberg here.

For the right direction, condition 2 says that there are countably many vertices, since you can just erase those of degree 2, and vertices of degree 1 clearly don'make any difference, planarity wise. So, now, we have a graph with countably many vertices, and thus countably many edges, such that any finite subgraph is planar. You want to show that the graph is planar. This is a simple compactness/Arzela-Ascoli type argument - something very similar (but stronger) is showed in the last section of I. Rivin, Combinatorial Optimization in Geometry Adv. in Appl. Math. 31 (2003), no. 1, 242–271. (There is a free arxiv.org version, in case that matters.)

$\endgroup$
  • $\begingroup$ It is the backward direction that I have problem with. Suppose the three condition holds, is there a pure graph theoretic reasoning to prove that the graph has to be planar? I have read the paper mentioned in the other post about two months ago but it is a bit too technical in some parts of it. $\endgroup$ – Guo Xian Yau Dec 27 '15 at 2:46
  • $\begingroup$ @GuoXianYau see the edit... $\endgroup$ – Igor Rivin Dec 27 '15 at 14:59
  • $\begingroup$ Thanks, I'm not very comfortable with geometry, but reading the paper does clear some of my doubts. I'll accept this answer for now. (: $\endgroup$ – Guo Xian Yau Dec 28 '15 at 2:33
  • $\begingroup$ I don't see how you can reduce to a graph with countably many vertices and edges. For example, let us start with the graph consisting of vertices $a$, $b$, and continuum many degree-2 vertices connected to $a$ and $b$. How does the reduction proceed? $\endgroup$ – Emil Jeřábek supports Monica Apr 14 '18 at 6:54

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.