Skip to main content
2 of 7
edited tags; edited title
Martin Sleziak
  • 4.7k
  • 4
  • 35
  • 40

Injection of Catalan objects into 3-connected planar graphs

Let $C_n = \frac{1}{n+1}\binom{2n}{n}$ be the $n$-th Catalan number, counting, for example, the number of (rooted) triangulations of the $(n+2)$-gon.

Let $P_n$ be the number of three-connected planar graphs on $n$-vertices, https://oeis.org/A000944.

If I am not mistaken, $C_{n-3} \leq P_n$ for $n\geq 4$. Eg., there are $C_2=2$ triangulations of the $4$-gon, and $2$ three-connected planar graphs on $5$ vertices.

Is there a nice injection?

Martin Rubey
  • 5.8k
  • 1
  • 24
  • 39