Subgraph embedded

87 Views Asked by At

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$.

1

There are 1 best solutions below

0
On BEST ANSWER

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.