2
$\begingroup$

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!

Improve this question
$\endgroup$
8
  • $\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
    Commented Oct 15, 2015 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$
    – user81529
    Commented Oct 15, 2015 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
    Commented Oct 22, 2015 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
    Commented Oct 22, 2015 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
    Commented Oct 24, 2015 at 20:14

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
0

You must log in to answer this question.