BMO 2022 shortlist

We divide the solution in two steps, first we prove that $k<3$, and then give an inductive construction of $P$ for $k=2$. Let $P$ have $V$ vertices, $E$ edges and $F$ faces. Suppose the contrary, that $k>2$. We have $k$ disjoint trees on $V$ vertices, so $E\ge 3(V-1)$. This is a contradiction as for every polyhedron we have $E\le 3V-6$.

Now we take $k=2$ and prove that for every positive integer $n$, we can find a convex polyhedron $P_{6n}$ with exactly $6n$ edges that satisfies the condition of the problem. For $n=1$, let's consider the tetrahedron $ABCD$. One colouring that works is: $AB$, $AD$ and $CD$ are in one colour, and $AC$, $BC$ and $BD$ are in the other colour.

Suppose we have constructed $P_{6n}$, here is how to construct $P_{6n+6}$: Consider the triangular face $T=xyz$ most recently added to $P_{6n}$, glue on top of $T$ a truncated pyramid whose larger base is $T$. We are effectively adding 3 new vertices, say $x^{\prime }$, $y^{\prime }$, $z^{\prime }$, 3 faces, and 6 edges, say $x{x}^{\prime }$, $y{y}^{\prime }$, $z{z}^{\prime }$, $x^{\prime }{y}^{\prime }$, $y^{\prime }{z}^{\prime }$, $z^{\prime }{x}^{\prime }$. We colour $x^{\prime }{y}^{\prime }$, $x^{\prime }{z}^{\prime }$, $y{y}^{\prime }$ with the first colour, and all other new edges with the second colour. It is now easy to see that in any one of the colours, a tree on the vertices of $P_{6n}$ in that colour, together with the newly added edges of that colour give a tree on the vertices of $P_{6n+6}$ in that colour.

Note that $x^{\prime }{y}^{\prime }{z}^{\prime }$ is the most recently added triangular face, so the construction can proceed inductively by glueing another truncated pyramid on top of it. It's easy to see (and prove inductively) that every vertex has degree 3 or 4, so condition (b) is satisfied and we are done.

---

Alternative solution.

For the construction we can also use Steinitz's Theorem on the characterization of convex polyhedra: A planar graph is the graph of a convex polyhedron if and only if it is 3-vertex connected. So we can take for example the graph on $\{v_1,v_2,\dots ,v_{2n}\}$ with edges $v_1{v}_2$, $v_2{v}_3$, $\dots$, $v_{2n-1}{v}_{2n}$ in one colour and $v_1{v}_3$, $v_2{v}_4$, $\dots$, $v_{2n-2}{v}_{2n}$ and $v_{2n}{v}_1$ in the other colour. It is easy to get a planar embedding of this graph as for example in the following figure for the case $n=4$.

This graph is 3-connected: Suppose we remove the vertices $v_i$ and $v_j$ with $i<j$. If $i=1$, $j=2$ or $i=2n-1$, $j=2n$ the remaining graph is obviously connected. If $1<i$ and $j=i+1<2n$ the remaining graph is also connected having the spanning path $v_{i-1}{v}_{i-2}\cdots v_1{v}_{2n}{v}_{2n-1}\cdots v_{i+1}$. Otherwise $j>i+1$ and we have the spanning path $v_1\cdots v_{i-1}{v}_{i+1}\cdots v_{j-1}{v}_{j+1}\cdots v_{2n}$.

This graph has $2n-2$ edges so for $n=1012$ it has the required number of edges. Furthermore it satisfies (b) as every vertex has degree 3 or 4.