<p>Suppose I have a non-Hamiltonian non-bipartite cubic planar graph $G_1$ = ($V_1$, $E_1$) where no face has fewer than five sides, and that I can partition $V_1$ into two Hamiltonian subgraphs.  Suppose further that $G_1$ has a set of faces that satisfies the Grinberg equation (remember that satisfaction of the Grinberg equation is a necessary but  not sufficient condition for a graph to be Hamiltonian), and is minimally two-connected, i.e., it contains exactly two edges, $v_1$ and $w_1$, whose removal disconnects $G_1$. Finally, assume that $G_1$ contains no separating triangles. Is there an example of such a $G_1$ that I can augment (judiciously) without limit by successively adding sets of vertices and edges to it in such a way that I create the series ($G_1$, $G_2$,...,$G_n$),  |$V_i$| &lt; |$V_j$|, <em>n</em> $\in$  $\mathbb{Z^+}$, where $G_i$ retains the given properties (including $v_1$and $w_1$) of $G_1$?</p>

CC BY-SA 3.0
2015-02-19T04:08:17.910Z
I'm not really sure what you mean by non-trivial, but Grinberg's theorem (https://en.wikipedia.org/wiki/Grinberg%27s_theorem) provides a way to make lots of 3-connected non-Hamiltonian cubic graphs without gadgets: just pack five- and eight-sided faces with three-fold symmetry so that the number of sides of the outer face is a multiple of three.
David Eppstein
CC BY-SA 3.0
2015-02-19T05:37:52.933Z
I am aware of Grinberg’s theorem. I should have added that I am looking for a scalable non-Hamiltonian $G$ that satisfies his formulation.
user2749107
<graph-theory>
Example of scalable non-Hamiltonian cubic planar graph
user2749107
# Example of scalable non-Hamiltonian cubic planar graph

(Asked by: username_0 on 2015-02-19)

Suppose I have a non-Hamiltonian non-bipartite cubic planar graph $G\_1$ = ($V\_1$, $E\_1$) where no face has fewer than five sides, and that I can partition $V\_1$ into two Hamiltonian subgraphs. Suppose further that $G\_1$ has a set of faces that satisfies the Grinberg equation (remember that satisfaction of the Grinberg equation is a necessary but not sufficient condition for a graph to be Hamiltonian), and is minimally two-connected, i.e., it contains exactly two edges, $v\_1$ and $w\_1$, whose removal disconnects $G\_1$. Finally, assume that $G\_1$ contains no separating triangles. Is there an example of such a $G\_1$ that I can augment (judiciously) without limit by successively adding sets of vertices and edges to it in such a way that I create the series ($G\_1$, $G\_2$,...,$G\_n$), |$V\_i$| < |$V\_j$|, *n* $\in$ $\mathbb{Z^+}$, where $G\_i$ retains the given properties (including $v\_1$and $w\_1$) of $G\_1$?

**Tags:** graph-theory

> **Comments:**
> **username_1**: I'm not really sure what you mean by non-trivial, but Grinberg's theorem (https://en.wikipedia.org/wiki/Grinberg%27s_theorem) provides a way to make lots of 3-connected non-Hamiltonian cubic graphs without gadgets: just pack five- and eight-sided faces with three-fold symmetry so that the number of sides of the outer face is a multiple of three.  
> **username_0**: I am aware of Grinberg’s theorem. I should have added that I am looking for a scalable non-Hamiltonian $G$ that satisfies his formulation.  

---

## 0 answers

