Let $G$ be a graph with disjoint copies of $K_{1,3}$. Prove that if there are uncountably many copies of $K_{1,3}$ in $G$, then $G$ is not planar.

I have a proof of this statement by contradiction i.e. assuming it is planar with uncountably many copies of $K_{1,3}$ in $G$, but I am not satisfied. I am wondering if anyone has a proof that proves the contrapositive i.e. if $G$ is planar, then there is only countably many copies of $K_{1,3}$ in $G$.

My idea is to find an embedding of $G$ onto $\mathbb{R}^2$ (or $\mathbb{C}$), and use the fact that $K_{1,3}$ has $3$ edges, and hence if we find disjoint open sets which contain each $K_{1,3}$, they will have positive measure.

Thanks a lot!

  • $\begingroup$ Fix an embedding of $G$. Come up with a notion of "size" of an embedded $K_{1,3}$. Show that you can only have finitely many $K_{1,3}$ of "size" 1 intersecting the unit square. $\endgroup$ – Anthony Quas Oct 15 '15 at 16:59
  • 1
    $\begingroup$ @AnthonyQuas The problem with this is that the "size" has to be something non-convention. For example for the usual measure, there can be uncountably infinite disjoint $C_3$ (cycle of length 3) that can be embedded within the unit square. $\endgroup$ – Guo Xian Yau Oct 15 '15 at 17:13
  • $\begingroup$ It's important here that by "disjoint" you mean vertex-disjoint. A planar graph can have uncountably many edge-disjoint copies of $K_{1,3}$. For instance, you can embed $K_{1,c}$ (where $c$ is the cardinality of the continuum) by placing the hub of the star at the origin, the leaves at every point of the unit circle, and the edges as line segments between each leaf and the origin; it has uncountably many edge-disjoint copies of $K_{1,3}$, for instance the ones formed by triples of leaves at angles of $2\pi/3$ from each other. $\endgroup$ – David Eppstein Oct 22 '15 at 20:09
  • $\begingroup$ What is your definition of "planar" for infinite graphs? Just that there is a continuous injection (not necessarily an embedding) from the graph to $\mathbb{R}^2$? $\endgroup$ – Eric Wofsey Oct 22 '15 at 22:05
  • 1
    $\begingroup$ The forbidden minor definition is the wrong definition of planar graphs for this result. For instance, a graph with uncountably many connected components, each of which contains a $K_{1,3}$, obeys the forbidden minor definition of planarity but also contains uncountably many vertex-disjoint $K_{1,3}$ subgraphs. I think the definition of planarity you should be using here is that you can map vertices to points in the plane and edges to curves connecting pairs of points so that the only intersections between pairs of edges or vertices and edges are when one vertex is an endpoint of an edge. $\endgroup$ – David Eppstein Oct 24 '15 at 20:14

This is a 1928 theorem of R. L. Moore "Concerning Triods in the Plane and the Junction Points of Plane Continua" PNAS Vol. 14, No. 1 (Jan. 15, 1928), pp. 85-88. Greg Kuperberg gave a nice proof of it here on MO.


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.