<p>Maybe I am mistaken but I think it is possible to make the example from <a href="https://math.stackexchange.com/a/78835/131224">https://math.stackexchange.com/a/78835/131224</a> Eulerian. Just take an octahedron and place 3 new vertices on each of its faces, connected to each other and also to two of the vertices of the face in a circular order. So if the face was $abc$, then add $def$ and connect $d$ to all but $a$, $e$ to all but $b$ and $f$ to all but $c$. The same reasoning works but now every degree is even.</p>

CC BY-SA 3.0
2014-04-11T15:16:11.430Z
We still need to check if it remains Non Hamiltonian - is that easy to see?
SamiD
CC BY-SA 3.0
2014-04-11T15:18:59.057Z
Besides I think this operation does not change the parity of the degrees.
SamiD
CC BY-SA 3.0
2014-04-11T18:41:37.697Z
It is easy to see that this is also Non-Hamiltonian; as the original octahedron had more faces than vertices, there is a face (of the original octahedron, now containing vertices) that we cannot enter. The parity of the degrees don't change, which is good, as they were all even in the beginning.
domotorp
CC BY-SA 3.0
2014-04-12T02:26:06.533Z
OK! so now I begin to understand the argument about the Kleetope. So what you are saying is that you add a triangle inside each of the original faces of an octahedron (instead of stellating it), this wuld introduce 3 vertices per face, so because the octahedron had 6 vertices and 8 faces, this new graph has 6 old vertices and 8x3 new vertices so since each of the 8 sets of vertices consumes at least one old vertex on the average we cannot have a Hamiltonian cycle. And the graph is clearly Eulerian - because the octahedron is. I think that is correct.
SamiD
CC BY-SA 3.0
2014-04-10T18:52:06.980Z
2014-04-10T18:52:06.980Z
2017-04-13T12:19:19.363Z
domotorp
<blockquote>
  <p>Is every Eulerian triangulated (planar) graph Hamiltonian?</p>
</blockquote>

<p>On the other hand we have that:</p>

<blockquote>
  <p><a href="http://en.wikipedia.org/wiki/Barnette%27s_conjecture" rel="nofollow noreferrer">Barnette's Conjecture</a> (Open): Every cubic bipartite (3-connected) planar graph is Hamiltonian.</p>
</blockquote>

<p>Notice that: Eulerian triangulated planar graphs and cubic bipartite planar graphs are mutual duals.</p>

<p>I would be happy to know of a proof or a counterexample (I have not been able to find either). In the absence of both is this a well known conjecture?</p>

<p>Some additional facts (possibly relevant):</p>

<ul>
<li>Every Eulerian triangulated planar graph is $3$-colorable (see <a href="http://www.math.uiuc.edu/~west/pubs/eultri.ps" rel="nofollow noreferrer">this</a>).</li>
<li>(<a href="http://en.wikipedia.org/wiki/Hamiltonian_path#Theorems_on_existence_of_Hamiltonian_cycles_in_planar_graphs" rel="nofollow noreferrer">Whitney's Theorem</a>) Every $4$-connected triangulated planar graph is Hamiltonian.</li>
</ul>

<p>Definitions:</p>

<ul>
<li>Hamiltonian Graph: Undirected Graph with a simple cycle through every vertex.</li>
<li>Eulerian Graph: Connected graph with all degrees even.</li>
<li>Triangulated (planar) Graph: Planar graph with every face a triangle.</li>
<li>Cubic Graph: Graph with every vertex having degree exactly $3$.</li>
</ul>

<p><strong>Edit:</strong> (Thanks@domotorp) Triangulated planar graphs are not necessarily Hamiltonian (e.g. see <a href="https://math.stackexchange.com/questions/78784/trivial-example-of-a-non-hamiltonian-planar-triangulation">this</a>)</p>

<reference-request><graph-theory><planar-graphs>
Dual Barnette's Conjecture
SamiD
# Dual Barnette's Conjecture

(Asked by: username_0 on 2014-04-10)

> Is every Eulerian triangulated (planar) graph Hamiltonian?

On the other hand we have that:

> [Barnette's Conjecture](http://en.wikipedia.org/wiki/Barnette%27s_conjecture) (Open): Every cubic bipartite (3-connected) planar graph is Hamiltonian.

Notice that: Eulerian triangulated planar graphs and cubic bipartite planar graphs are mutual duals.

I would be happy to know of a proof or a counterexample (I have not been able to find either). In the absence of both is this a well known conjecture?

Some additional facts (possibly relevant):

* Every Eulerian triangulated planar graph is $3$-colorable (see [this](http://www.math.uiuc.edu/~west/pubs/eultri.ps)).
* ([Whitney's Theorem](http://en.wikipedia.org/wiki/Hamiltonian_path#Theorems_on_existence_of_Hamiltonian_cycles_in_planar_graphs)) Every $4$-connected triangulated planar graph is Hamiltonian.

Definitions:

* Hamiltonian Graph: Undirected Graph with a simple cycle through every vertex.
* Eulerian Graph: Connected graph with all degrees even.
* Triangulated (planar) Graph: Planar graph with every face a triangle.
* Cubic Graph: Graph with every vertex having degree exactly $3$.

**Edit:** (Thanks@domotorp) Triangulated planar graphs are not necessarily Hamiltonian (e.g. see [this](https://math.stackexchange.com/questions/78784/trivial-example-of-a-non-hamiltonian-planar-triangulation))

**Tags:** reference-request, graph-theory, planar-graphs

---

## 1 answers

### Answer by username_1 on 2014-04-10. Score: 4 | Accepted answer

Maybe I am mistaken but I think it is possible to make the example from <https://math.stackexchange.com/a/78835/131224> Eulerian. Just take an octahedron and place 3 new vertices on each of its faces, connected to each other and also to two of the vertices of the face in a circular order. So if the face was $abc$, then add $def$ and connect $d$ to all but $a$, $e$ to all but $b$ and $f$ to all but $c$. The same reasoning works but now every degree is even.

> **Comments:**
> **username_0**: We still need to check if it remains Non Hamiltonian - is that easy to see?  
> **username_0**: Besides I think this operation does not change the parity of the degrees.  
> **username_1**: It is easy to see that this is also Non-Hamiltonian; as the original octahedron had more faces than vertices, there is a face (of the original octahedron, now containing vertices) that we cannot enter. The parity of the degrees don't change, which is good, as they were all even in the beginning.  
> **username_0**: OK! so now I begin to understand the argument about the Kleetope. So what you are saying is that you add a triangle inside each of the original faces of an octahedron (instead of stellating it), this wuld introduce 3 vertices per face, so because the octahedron had 6 vertices and 8 faces, this new graph has 6 old vertices and 8x3 new vertices so since each of the 8 sets of vertices consumes at least one old vertex on the average we cannot have a Hamiltonian cycle. And the graph is clearly Eulerian - because the octahedron is. I think that is correct.  

---

