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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.)

Improve this answer
$\endgroup$
4
  • $\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$
    – user81529
    Commented Dec 27, 2015 at 2:46
  • $\begingroup$ @GuoXianYau see the edit... $\endgroup$
    – Igor Rivin
    Commented Dec 27, 2015 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$
    – user81529
    Commented Dec 28, 2015 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
    Commented Apr 14, 2018 at 6:54

You must log in to answer this question.