<p>I have a partial solution, with constructions for the first question and for the second question when <span class="math-container">$n = 2\ (\text{mod}\ 4)$</span>.</p>

<p>Here are constructions for <span class="math-container">$n = 8$</span> and <span class="math-container">$n = 14$</span>. These generalise to constructions for <span class="math-container">$n = 0\ (\text{mod}\ 4)$</span> and <span class="math-container">$n = 2\ (\text{mod}\ 4)$</span>, by taking any square, for example 1,2,3,6 in the second construction, and replacing it with a ladder like shown in the third image.</p>

<p>For the second question, the <span class="math-container">$2\ (\text{mod}\ 4)$</span> construction has no nontrivial automorphisms when <span class="math-container">$n \geq 18$</span>, as we can recover the labeling. First find the added ladder and the pairs 1-2 and 3-6. To discern between them, note that the nodes 1 and 2 are not in any four-node cycle except in the ladder, while 1 and 6 are. Similarly 2 and 3 are not in a four-node cycle except in the ladder, while 1 and 6 are. Then you can uniquely discern 4 (only non-ladder node connected to 1), 5 (same for 6), 8 (only node connected to 3 and 5) and so on.</p>

<p><a href="https://i.sstatic.net/gIdG5.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/gIdG5.png" alt="construction for 0 mod 4"></a>
<a href="https://i.sstatic.net/cE8ta.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/cE8ta.png" alt="construction for 2 mod 4"></a>
<a href="https://i.sstatic.net/yqmq1.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/yqmq1.png" alt="construction for 2 mod 4 with ladder"></a></p>

CC BY-SA 4.0
2019-12-15T12:28:23.180Z
2019-12-15T12:28:23.180Z
Antti Röyskö
<p>Consider the class C3CBP of <span class="math-container">$3$</span>-connected cubic bipartite planar graphs. They form the class on which the (in)famous <a href="https://en.m.wikipedia.org/wiki/Barnette%27s_conjecture" rel="nofollow noreferrer">Barnette’s  conjecture</a> is based. My interest in C3CBP graphs is somewhat orthogonal to this:</p>

<p>My questions are:</p>

<ol>
<li>Does there exist a C3CBP graph on <span class="math-container">$n$</span> vertices for every even <span class="math-container">$n &gt; n_0$</span> where <span class="math-container">$n_0$</span> is some small constant?</li>
<li>Does there exist a C3CBP graph without any non trivial automorphisms on <span class="math-container">$n$</span> vertices for every even <span class="math-container">$n &gt; n_1$</span> where <span class="math-container">$n_1$</span> is some small constant?</li>
</ol>

<p>Notice that <span class="math-container">$3$</span>-connected planar graphs have only at most linear sized automorphism groups so the second question is natural. </p>

<p>I need the existence and explicit construction of such graphs in an algorithmic problem apparently unrelated to Barnette’s conjecture.</p>

<graph-theory><graph-algorithms><co.combinatorics>
Existence of graphs of every order related to Barnette’s conjecture
SamiD
# Existence of graphs of every order related to Barnette’s conjecture

(Asked by: username_0 on 2019-12-14)

Consider the class C3CBP of $3$-connected cubic bipartite planar graphs. They form the class on which the (in)famous [Barnette’s conjecture](https://en.m.wikipedia.org/wiki/Barnette%27s_conjecture) is based. My interest in C3CBP graphs is somewhat orthogonal to this:

My questions are:

1. Does there exist a C3CBP graph on $n$ vertices for every even $n > n\_0$ where $n\_0$ is some small constant?
2. 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.

**Tags:** graph-theory, graph-algorithms, co.combinatorics


---

## 1 answers

### Answer by username_1 on 2019-12-15. Score: 2 | Accepted answer

I have a partial solution, with constructions for the first question and for the second question when $n = 2\ (\text{mod}\ 4)$.

Here are constructions for $n = 8$ and $n = 14$. These generalise to constructions for $n = 0\ (\text{mod}\ 4)$ and $n = 2\ (\text{mod}\ 4)$, by taking any square, for example 1,2,3,6 in the second construction, and replacing it with a ladder like shown in the third image.

For the second question, the $2\ (\text{mod}\ 4)$ construction has no nontrivial automorphisms when $n \geq 18$, as we can recover the labeling. First find the added ladder and the pairs 1-2 and 3-6. To discern between them, note that the nodes 1 and 2 are not in any four-node cycle except in the ladder, while 1 and 6 are. Similarly 2 and 3 are not in a four-node cycle except in the ladder, while 1 and 6 are. Then you can uniquely discern 4 (only non-ladder node connected to 1), 5 (same for 6), 8 (only node connected to 3 and 5) and so on.

[![construction for 0 mod 4](https://i.sstatic.net/gIdG5.png)](https://i.sstatic.net/gIdG5.png)
[![construction for 2 mod 4](https://i.sstatic.net/cE8ta.png)](https://i.sstatic.net/cE8ta.png)
[![construction for 2 mod 4 with ladder](https://i.sstatic.net/yqmq1.png)](https://i.sstatic.net/yqmq1.png)


---

