Consider the class C3CBP of $3$-connected cubic bipartite planar graphs. They form the class on which the (in)famous Barnette’s conjecture is based. My interest in C3CBP graphs is somewhat orthogonal to this:
My questions are:
- Does there exist a C3CBP graph on $n$ vertices for every even $n > n_0$ where $n_0$ is some small constant?
- Does there exist a C3CBP graph without any non trivial automorphisms on $n$ vertices for every even $n > n_1$ where $n_1$ is some small constant?
Notice that $3$-connected planar graphs have only at most linear sized automorphism groups so the second question is natural.
I need the existence and explicit construction of such graphs in an algorithmic problem apparently unrelated to Barnette’s conjecture.