1
$\begingroup$

Suppose I have a planar graph (without loops, vertices of degree one or multiple edges) such that each face (including external) has six edges and there ther ore no two adjacent vertices with degree two.

Examining some examples I found that each such graph has at least one of the following two subgraphs embedded:

enter image description here

enter image description here

Is it true for every such graph?

What I figured out is that if the graph have $n$ faces (including external one), then:

$2v_2+v_3\geqslant 2n+8$,

where $v_i$ be the number of vertices of degree $i$.

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Take the octahedral graph. This graph is planar, 4-regular and triangulated. Split each edge by a 2-degree vertex, and you get a counter example.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .