Packing and covering odd cycles in cubic plane graphs with small faces
Diego Nicodemos Matěj Stehlík





matrix,arrows,calc



theoremTheorem[section]
lemma[theorem]Lemma
observation[theorem]Observation
proposition[theorem]Proposition
corollary[theorem]Corollary
conjectureConjecture

definition
definition[theorem]Defintion

equationsection
figuresection













tikzgraph
  
      [vertex/.style=circle, draw=black, fill, inner sep=0mm,
      minimum size=3pt,edge/.style=semithick,
       subdivision/.style=circle, draw=black, fill=white, inner sep=0mm,
       minimum size=3pt,edge/.style=semithick]
  


Odd cycles in cubic plane graphs]Packing and covering odd cycles in cubic plane graphs with small faces

The first author was partially supported by CAPES and CNPq.
Colégio Pedro II, COPPE/Sistemas, Universidade Federal do Rio
  de Janeiro, Brazil
nicodemos@cos.ufrj.br

The second author was partially supported by ANR project Stint (ANR-13-BS02-0007), ANR
project GATO (ANR-16-CE40-0009-01), and by LabEx PERSYVAL-Lab (ANR-11-LABX-0025).
Laboratoire G-SCOP, Univ. Grenoble Alpes, France
matej.stehlik@grenoble-inp.fr



  We show that any 3-connected cubic plane graph on n vertices,
  with all faces of size at most 6, can be made bipartite by deleting
  no more than √((p+3t)n/5) edges, where p and t are the numbers
  of pentagonal and triangular faces, respectively. In particular, any such
  graph can be made bipartite by deleting at most √(12n/5) edges.
  This bound is tight, and we characterise the extremal graphs. We deduce
  tight lower bounds on the size of a maximum cut and a maximum independent
  set for this class of graphs. This extends and sharpens the results of
  Faria, Klein and Stehlík [SIAM J. Discrete Math. 26 (2012) 1458–1469].


[
    Matěj Stehlík
    
=================





§ INTRODUCTION


A set of edges intersecting every odd cycle in a graph is known as an
odd cycle (edge) transversal, or odd cycle cover, and the
minimum size of such a set is denoted by τ_. A set of edge-disjoint
odd cycles in a graph is called a packing of odd cycles, and the maximum
size of such a family is denoted by ν_. Clearly, τ_≥ν_.
Dejter and Neumann-Lara <cit.> and independently
Reed <cit.> showed that in general, τ_ cannot be bounded
by any function of ν_, i.e., they do not satisfy the
Erdős–Pósa property. However, for planar graphs, Král' and
Voss <cit.> proved the (tight) bound τ_≤ 2ν_.

In this paper we focus on packing and covering of odd cycles in 3-connected
cubic plane graphs with all faces of size at most 6. Such graphs—and their
dual triangulations—are a very natural class to consider, as they correspond
to surfaces of genus 0 of non-negative curvature (see e.g. <cit.>).

A much-studied subclass of cubic plane graphs with all faces of size at most 6
is the class of fullerene graphs, which only have faces of size 5 and 6.
Faria, Klein and Stehlík <cit.> showed that any fullerene
graph on n vertices has an odd cycle transversal with no more than
√(12n/5) edges, and characterised the extremal graphs. Our main result
is the following extension and sharpening of their result to all 3-connected cubic
plane graphs with all faces of size at most 6.



  Let G be a 3-connected cubic plane graph on n vertices with all faces of size at most
  6, with p pentagonal and t triangular faces. Then
  
    τ_(G) ≤√((p+3t)n/5).

  In particular, τ_(G) ≤√(12n/5) always holds, with equality
  if and only if all faces have size 5 and 6, n=60k^2 for some
  k ∈, and (G) ≅ I_h.


If G is a fullerene graph, then t=0 and Euler's formula implies that p=12, so
Theorem <ref> does indeed generalise the result of Faria, Klein and Stehlík <cit.>.
We also remark that the smallest 3-connected cubic plane graph with all faces of size at most 6
achieving the bound τ_(G) = √(12n/5) in Theorem <ref> is the ubiquitous
buckminsterfullerene graph (on 60 vertices).

The rest of the paper is organised as follows. In Section <ref>,
we introduce the basic notation and terminology, as well as the key concepts from
combinatorial optimisation and topology. In Section <ref>, we introduce
the notions of patches and moats, and prove bounds on the area of moats. Then, in
Section <ref>, we use these bounds to
prove an upper bound on the maximum size of a packing of T-cuts in triangulations
of the sphere with maximum degree at most 6. Using a theorem of Seymour <cit.>,
we deduce, in Section <ref>, an upper bound on the minimum
size of a T-join in triangulations of the sphere with maximum degree at most 6,
and then dualise to complete the proof of Theorem <ref>. In
Section <ref>, we deduce lower bounds on the size of a maximum cut and
a maximum independent set in 3-connected cubic plane graphs with no faces of size
more than 6. Finally, in Section <ref>, we show why the condition
on the face size cannot be relaxed, and briefly discuss the special case when the graph
contains no pentagonal faces.



§ PRELIMINARIES



Most of our graph-theoretic terminology is standard and follows <cit.>.
All graphs are finite and simple, i.e., have no loops and parallel edges.
The degree of a vertex u in a graph G is denoted by d_G(u).
If all vertices in G have degree 3, then G is a cubic graph.
The set of edges in G with exactly one end vertex in X is denoted by δ_G(X).
A set C of edges is a cut of G if C=δ_G(X), for some X ⊆ V(G).
When there is no risk of ambiguity, we may omit the subscripts in the above notation.

The set of all automorphisms of a graph G forms a group, known as the automorphism group
(G). The full icosahedral group I_h ≅ A_5 × C_2 is the group of
all symmetries (including reflections) of the regular icosahedron. The full tetrahedral
group T_d ≅ S_4 is the group of all symmetries (including reflections) of the regular
tetrahedron.

A polygonal surface K is a simply connected 2-manifold, possibly with a boundary,
which is obtained from a finite collection of disjoint simple polygons in ^2 by
identifying them along edges of equal length. We denote by |K| the union of all polygons in
K, and remark that |K| is a surface.

Based on this construction, K may be viewed as a graph embedded in the
surface |K|. Accordingly, we denote its set of vertices, edges, and faces
by V(K), E(K), and F(K), respectively. If every face of K is incident to three edges,
K is a triangulated surface, or a triangulation of |K|.
In this case, K can be viewed as a simplicial complex.
If K is a simplicial complex and X ⊆ V(K),
then K[X] is the subcomplex induced by X, and K∖ X is the subcomplex
obtained by deleting X and all incident simplices. If L is a subcomplex of K,
then we simply write K ∖ L instead of K ∖ V(L).

If K is a graph embedded in a surface |K| without boundary, the dual graph
K^* is the graph with vertex set F(K), such that fg ∈ E(K^*) if and only if f and
g share an edge in K. The size of a face f ∈ F(K) is defined as the number
of edges on its boundary walk, and is denoted by d_K(f). Note that d_K(f)=d_K^*(f^*).

Any polygonal surface homeomorphic to a sphere corresponds to a plane
graph via the stereographic projection. Therefore, terms such as `plane triangulation'
and `triangulation of the sphere' can be used interchangeably.
We shall make the convention to use the term `cubic plane graphs' because it is so
widespread, but refer to the dual graphs as `triangulations of the sphere' because
it reflects better our geometric viewpoint.

Given a polygonal surface K, the boundary ∂ K is the set of all
edges in K which are not incident to two triangles; the number of edges in the
boundary is denoted by |∂ K|. With a slight abuse of notation, ∂ K will also denote
the set of vertices incident to edges in ∂ K. The set of interior vertices
is defined as (K)=V(K)∖∂ K.

Given a triangulated surface K, we define K to be the number of faces in K,
and the combinatorial curvature of K as ∑_u ∈(K)(6-d_K(u)).
Recall that the Euler characteristic
χ(K) of a polygonal surface K is equal to |V(K)|-|E(K)|+|F(K)|. It can be shown
that χ is a topological invariant: it only depends on the surface |K|, not on the
polygonal decomposition of K. If X is any contractible space, then χ(X)=1, and
if S^2 is the standard 2-dimensional sphere, then χ(S^2)=2. The following lemma
is an easy consequence of Euler's formula and double counting, and we leave its verification
to the reader.



  Let K be a triangulated surface with (a possibly empty) boundary ∂ K. Then
  
    ∑_v ∈ K(6-d(v))+∑_v ∈∂ K(4-d(v))=6χ(K).



We remark that, if we multiply both sides of the equation by π/3, we obtain a discrete
version of the Gauss–Bonnet theorem (see e.g. <cit.>), where the curvature is concentrated at the vertices. 

In order to prove Theorem <ref>, it is more convenient to work with the dual
graphs, which are characterised by the following simple lemma. The proof is an easy
exercise, which we leave to the reader.



  If G is a 3-connected simple cubic plane graph with all faces of size at most 6, then the dual
  graph G^* is a simple triangulation of the sphere with all vertices of degree at
  least 3 and at most 6.


We will use the following
important concept from combinatorial optimisation. Given a graph G=(V,E) with a distinguished
set T of vertices of even cardinality, a T-join of G is a subset J ⊆ E
such that T is equal to the set of odd-degree vertices in (V,J). The minimum size of a
T-join of G is denoted by τ(G,T). When T is the set of odd-degree vertices of G,
a T-join is known as a postman set. A T-cut is an edge cut δ(X) such
that |T∩ X| is odd. A packing of T-cuts is a disjoint collection
δ(ℱ)={δ(X) | X ∈ℱ} of T-cuts of G; the maximum
size of a packing of T-cuts is denoted by ν(G,T).

A family of sets ℱ is said to be laminar if, for every pair
X,Y ∈ℱ, either X ⊆ Y, Y ⊆ X, or X ∩ Y = ∅.
A T-cut δ(X) is inclusion-wise minimal if no T-cut is properly contained
in δ(X). For more information on T-joins
and T-cuts, the reader is referred to <cit.>.



§ PATCHES AND MOATS



From now on assume that K is a triangulation of the sphere with all vertices of degree at most 6.
We define a subcomplex L ⊆ K to be a patch if in the dual complex K^*, the faces
corresponding to V(L) form a subcomplex homeomorphic to a disc. (Equivalently, one could say
that L ⊆ K is a patch if L is an induced, contractible subcomplex of K.)
A patch L⊆ K such that c=∑_u ∈ V(L)(6-d_K(u)) is called a c-patch.
We remark that a c-patch L has combinatorial curvature c if and only if all vertices in the
boundary ∂ L have degree 6 in K.
If u ∈ V(K) has degree 6-c, and the set X of vertices at distance at most r from u
contains only vertices of degree 6, then the c-patch K[{u}∪ X] is denoted by D_r(c).
The subcomplex of the dual complex K^* formed by the faces in V(D_r(c)) is denoted by D^*_r(c);
see Figure <ref>.



The following isoperimetric inequality follows from the work of
Justus <cit.>[Gunnar Brinkmann <cit.>
has pointed out an error in the statement and proof of <cit.>
on which <cit.> is based, but has sketched a different way to prove
<cit.>.].



  Let K^* be a polygonal surface homeomorphic to a disc, with all internal vertices of
  degree 3 and with n faces, all of size at most 6. Let c=∑_f ∈ F(K^*)(6-d(f)),
  and suppose that c ≤ 5. Then
  
    |∂ K^*| ≥√(8(6-c)(n-1)+(6-c)^2).

  Equality holds if K^* ≅ D^*_r(c), for some integer r ≥ 0, and only
  if at most one face in K^* has size less than 6.



  The minimum possible values of |∂ K^*| are given in <cit.>,
  for all possible numbers of hexagonal, pentagonal, square, and triangular faces.
  In each case, our bound is satisfied. Moreover, it can be checked that equality
  holds only if at most one face in K^* has size less than 6. Finally, if
  K^* ≅ D^*_r(c), then it can be shown that |∂ K^*|=(6-c)(2r+1) and
  f-1=(6-c)r(r+1)/2. Hence, |∂ K^*| = √(8(6-c)(f-1)+(6-c)^2).


We can use Lemma <ref> to deduce the following isoperimetric inequality
for triangulations. Certain special cases of the inequality were already proved by
Justus <cit.>.



  Let K be a triangulation of the sphere with all vertices of degree at most 6,
  and let L ⊆ K be a patch of combinatorial curvature c ≤ 5. Then
  
    |∂ L| ≥√((6-c)  L).

  Equality holds if L ≅ D_r(c), for some integer r ≥ 0, and only
  if at most one vertex in L has degree less than 6.



  Put n=|V(K)|, and let L^* be the subcomplex of K^* formed by the faces
  corresponding to V(L). By Lemma <ref>,
  
    |∂ L^*| ≥√(8(6-c)(n-1)+(6-c)^2).

  Moreover, the following two equalities were shown by Justus <cit.>
  
    2(n-1)= L-|∂ L|,

  
    |∂ L|^2 = 14|∂(L^*)|^2+(6-c)|∂ L|-14(6-c)^2.

  So, combining (<ref>), (<ref>) and (<ref>) gives
  
    |∂ L|^2 ≥ (6-c)  L.

  
  Equality holds in (<ref>) if and only if equality holds in (<ref>). The
  latter is true only if at most one face in L^* has size less than 6, or equivalently,
  only if at most one vertex in L has degree less than 6. For the final
  part, it is enough to note that if L ≅ D_r(c), then L^* ≅ D^*_r(c), so
  equality holds in (<ref>) and therefore in (<ref>).


Let L ⊆ K be a patch. A moat of width 1 in K surrounding L
is the set ^1(L) of all the faces in F(K)∖ F(L) with at
least one vertex in V(K). More generally, we can define a moat of width w in K surrounding
L recursively as ^w(L)=^1(^w-1(L)∪ L). With a slight abuse of notation,
^w(L) will also denote the subcomplex of K formed by the faces in ^w(L).
If L is a c-patch, then ^w(L) is a c-moat of width w surrounding L.
See Figure <ref> for an example of a moat.



Under certain conditions, the area of a c-moat ^w(L) can be bounded
in terms of c, w, and L.



  Let K be a triangulation of the sphere with maximum degree at most 6,
  and suppose L ⊆ K is a c-patch, for some 0<c<6.
  If L∪^i(L) is a c-patch, for every 0≤ i ≤ w-1, then
  
    ^w(L)≥ (6-c)w^2+2w√((6-c)  L).

  Equality holds if L ≅ D_r(c), for some integer r ≥ 0, and only
  if at most one vertex in L has degree less than 6.



  As L is contractible, its Euler characteristic is χ(L)=1.
  We have
  
    c    = ∑_u ∈ V(L)(6-d_K(u))
       = ∑_u ∈ L(6-d_L(u))+∑_u ∈∂ L(6-d_L(u))-^1(L)
       = ∑_u ∈ L(6-d_L(u))+∑_u ∈∂ L(4-d_L(u))+2|∂ L|-^1(L).

  Hence, by Lemma <ref>,
  
    2|∂ L|+6-c = ^1(L).

  
  The dual complex K^* is homeomorphic to the sphere and the subcomplex L^*
  formed by the faces corresponding to V(L) is homeomorphic to a disc, so by the
  Jordan–Schoenflies theorem, the subcomplex formed by the faces corresponding
  to V(K)∖ V(L) is also homeomorphic to a disc. Hence, K ∖ L is
  also a patch. Moreover, K has Euler characteristic χ(K)=2, so by
  Lemma <ref>, ∑_u ∈ V(K)(6-d(u))=12. Therefore,
  ∑_u ∈ V(K∖ L)(6-d_K(u))=12-c, i.e., K ∖ L is a
  (12-c)-patch. Applying (<ref>) to L and to
  K∖ L,
  
    2|∂ L|+6-c    = ^1(L)
       = ^1(K∖ L)
       = 2|∂(K∖ L)|+6-(12-c).

  Hence, |∂(L ∪^1(L))|=|∂(K∖ L)|=|∂ L|+6-c, so by
  induction, and the fact that L ∪^i(L) is a patch for all 0 ≤ i ≤ w-1,
  
    |∂(L ∪^i(L))|=|∂ L|+(6-c)i.

  By (<ref>) and (<ref>),
  
    ^1(L ∪^i(L))   = 2|∂(L ∪^i(L))|+6-c 
       = 2(|∂ L|+(6-c)i)+6-c 
       = 2|∂ L|+(6-c)(2i+1),

  so the area of ^w(L) is
  
    ^w(L)   = ∑_i=0^w-1^1(L ∪^i(L))
       = ∑_i=0^w-1(2|∂ L|+(6-c)(2i+1))
       = 2w|∂ L|+(6-c)w^2.

  The combinatorial curvature of L is at most c, so by Lemma <ref>,
  
    |∂ L| ≥√((6-c)  L),

  with equality if L ≅ D_r(c), for some integer r ≥ 0, and only
  if at most one vertex in L has degree less than 6.




§ PACKING ODD CUTS IN TRIANGULATIONS OF THE SPHERE WITH MAXIMUM DEGREE AT MOST 6



We now relate certain special types of packings of T-cuts to packings of
1-, 3- and 5-moats.



  Let K be a triangulation of the sphere with all vertices of degree at most 6,
  and let T be the set of odd-degree vertices in K. There exists a family
  ℱ on V(K) and a vector w ∈^|ℱ| with the following
  properties.
  
    
  *  ℳ=⋃_X ∈ℱ_K^w_X(X) is a packing of
      moats in K;
    
  *  The total width of ℳ is ∑_X ∈ℱw_X=ν(K,T);
    
  *  For every X ∈ℱ, the subcomplex K[X] is a patch;
    
  *  Every ^w_X(X) ∈ℳ is a 1-, 3-, or 5-moat in K;
    
  *  If X is an inclusion-wise minimal element in ℱ, then |X|=1;
    
  *  ℱ is laminar.
  



  Consider a packing δ(ℱ') of inclusion-wise minimal T-cuts in K of size
  of ν(K,T). Note that ∑_u ∈ X(6-d_K(u)) is odd, for every X ∈ℱ.
  Since ∑_u ∈ X(6-d_K(u))=12 and δ(X)=δ(V(K)∖ X), we can assume that
  ∑_u ∈ X(6-d_K(u))≤ 5; otherwise we could replace X by V(K)∖ X in
  δ(ℱ'). Finally, we can also assume that,
  subject to the above conditions, ℱ' minimises ∑_X ∈ℱ' |X|.
  
  We remark that ℱ' is a laminar family. Indeed, suppose that X,Y ∈ℱ',
  X ∩ Y ≠∅, X ⊈Y and Y ⊈X. Then
  ^1(X)∩^1(Y)≠∅, so there is a face {u,v,w} of K in
  ^1(X)∩^1(Y). Since
  
    |δ(X)∩{uv,uw,vw}|=|δ(Y)∩{uv,uw,vw}| = 2,

  it follows that δ(X)∩δ(Y)≠∅, contradicting the fact that
  ℱ' is a packing of T-cuts. Hence, ℱ' is laminar.

  We summarise the properties of the family ℱ' below.
  
    
  *  δ(ℱ') is a packing of T-cuts;
    
  *  |ℱ'|=ν(K,T);
    
  *  δ(X) is an inclusion-wise minimal cut,
      for every X ∈ℱ';
    
  *  ∑_u ∈ X(6-d_K(u)) ∈{1,3,5} for all X ∈ℱ';
    
  *  Subject to <ref>–<ref>, ℱ'
      minimises ∑_X ∈ℱ' |X|;
    
  *  ℱ' is laminar.
  
  
  We let ℱ be the subfamily of ℱ' consisting of the
  elements X ∈ℱ' such that
  
    ∑_u ∈ Y(6-d_K(u))<∑_u ∈ X(6-d_K(u)),

  for every Y ∈ℱ such that Y ⊆ X.
  For each X ∈ℱ, let
  
    ℱ'_X={Y ∈ℱ' : X ⊆ Y, ∑_u ∈ Y(6-d_K(u))=∑_u ∈ X(6-d_K(u))},

  and let w_X=|F'_X|.
  
  To prove <ref>, we use an argument very similar to the one we used to
  prove <ref>.
  Clearly, for every X ∈ℱ, ^w_X(X)=⋃_Y ∈ℱ'_X^1(Y)
  is a moat around X of width w_X. Let X,Y ∈ℱ, and suppose that
  ^w_X(X) ∩^w_Y(Y) ≠∅. Then there exists a face
  {u,v,w}∈ F(K) and sets X',Y' ∈ℱ' such that X ⊆ X',
  Y ⊆ Y', and
  
    |δ(X')∩{uv,uw,vw}|=|δ(Y')∩{uv,uw,vw}| = 2.

  But then δ(X') ∩δ(Y') ≠∅, so by <ref>,
  X'=Y'. Hence, by the construction of ℱ, X=Y. This proves <ref>.
  
  To prove <ref>, it suffices to note that ∑_X ∈ℱw_X=|ℱ'|=ν(K,T)
  by <ref>.
  
  The property <ref> follows immediately from <ref>;
  indeed, since δ(X) is
  an inclusion-wise minimal cut, the dual edges form a cycle, so by the
  Jordan–Schoenflies theorem, the subcomplex of K^* formed by the faces in
  X is homeomorphic to a disc, so K[X] is a patch.

  Since ℱ⊆ℱ', <ref> follows immediately
  from <ref> and  <ref> follows immediately from <ref>.
  
  To prove <ref>, let X be an inclusion-wise minimal element
  of ℱ. By the definition of ℱ, X is also an inclusion-wise
  minimal element of ℱ'. Since ∑_u ∈ Xd(u) is odd, at least one
  vertex in X has odd degree. If |X|>1, let u be a vertex of odd degree in X,
  and let ℱ”=(ℱ'∖ X) ∪{u}. Then ℱ” satisfies
  <ref>–<ref>, but ∑_X ∈ℱ” |X|<∑_X ∈ℱ' |X|,
  contradicting <ref>.


Lemmas <ref> and <ref> can be used to prove
the following upper bound on the maximum size of a packing of odd cuts in
spherical triangulations with all vertices of degree at most 6,
which may be of independent iterest. By taking the planar dual, we also get
an upper bound on ν_ for the class of 3-connected cubic plane
graphs with all faces of size at most 6.


  Let K be a triangulation of the sphere with maximum degree
  at most 6. If T is the set of odd-degree vertices of K, then
  
    ν(K,T) ≤√( 15∑_u ∈ T(6-d(u))  K).

  In particular, ν(K,T) ≤√(12  K/5) always holds,
  with equality if and only if all vertices have degree 5 and 6, K=60k^2
  for some k ∈, and (K) ≅ I_h.



  Let ℳ=⋃_X ∈ℱ_K^w_X(X) be a packing of 1-, 3- and
  5-moats in K of total width ∑_X ∈ℱw_X=ν(K,T), as
  guaranteed by Lemma <ref>. Let m_c be the total area of
  c-moats of ⋃_X ∈ℱ_K^w_X(X), where
  c∈{1,3,5}. Define the incidence vectors r, s, t ∈ℝ^|T|  as
  follows: for every u ∈ T, let r_u, s_u, t_u be the width of the 1-moat,
  3-moat and 5-moat surrounding u, respectively.

  Define the inner product ⟨·,·⟩ on ^|T| by
  ⟨ x,y ⟩ = ∑_u∈ T(6-d(u)) x_uy_u and the norm
  · by x=⟨ x,x ⟩. With this inner product,
  the total width of 1-, 3- and 5-moats in
  ⋃_X ∈ℱ_K^w_X(X) can be expressed as
  ⟨ r,1⟩, 13 ⟨ s,1⟩, and
  15 ⟨ t,1⟩, respectively. Therefore,
  
    ν(K,T)=∑_X ∈ℱw_X=⟨ r+13s+15t,1⟩.


  To prove the inequality in Theorem <ref>, we compute lower bounds on
  m_1, m_3 and m_5 in terms of the vectors r, s and t, and then use
  the fact that the moats are disjoint, so the sum m_1+m_3+m_5 cannot exceed f,
  the number of faces of K. Simplifying the inequality gives the desired bound.
  
  To bound m_1, recall that by property <ref> of Lemma <ref>,
  every 1-moat in ℳ is of the form _K^r_u(u), where u is a
  5-vertex in K. By Lemma <ref>,
  
    _K^r_u(u) = (6-(6-d(u)))r_u^2= 5r_u^2,

  and summing over all 1-moats gives the equality
  
    m_1 = 5 ∑_u∈ T(6-d(u))r_u^2 = 5r^2.


  To bound m_3, let _K^s_u(X) be a non-empty 3-moat in ℳ, for
  some u∈ T ∩ X. By the laminarity of ℳ, the 3-patch K[X] contains
  the (possibly empty) 1-moats _K^r_u(u), for all 5-vertices
  u ∈ T ∩ X. All the moats are pairwise disjoint, so by (<ref>)
  and the Cauchy–Schwarz inequality,
  
    K[X]   ≥∑_u ∈ T ∩ X_K^r_u(u)
       ≥ 5 ∑_u∈ T ∩ X(6-d(u))r_u^2
       ≥5(∑_u∈ T ∩ X(6-d(u))r_u)^2/∑_u ∈ T ∩ X (6-d(u))
       ≥5/3(∑_u∈ T ∩ X(6-d(u))r_u)^2.

  Hence, by Lemma <ref>,
  
    _K^s_u(X)   ≥ 3s_u^2+2s_u√(3 K[X])
       ≥∑_u∈ T  ∩ X(6-d(u))s_u^2+2√(5)∑_u ∈ T
            ∩ X(6-d(u))r_us_u .

  Summing over all 3-moats gives the inequality
  
    m_3 ≥s^2+2√(5)⟨ r,s ⟩.


  To bound m_5, let _K^t_u(Y) be a non-empty 5-moat in ℳ, for
  some u∈ T∩ Y. By the laminarity of ℳ, the 5-patch K[Y] contains at most one
  non-empty 3-moat _K^s_u(X) of ℳ. All the moats are pairwise disjoint,
  so by (<ref>), (<ref>) and the Cauchy–Schwarz
  inequality,
  
    K[Y]   ≥∑_u∈ T ∩ Y_K^r_u(u)+
                ∑_u∈ T ∩ Y_K^s_u(X)
       ≥ 5 ∑_u∈ T ∩ Y(6-d(u))r_u^2+∑_u ∈ T ∩ Y
                (6-d(u))(2√(5)r_us_u+s_u^2)
       =    5 ∑_u∈ T ∩ Y(6-d(u))(r_u+1√(5)
                s_u)^2
       ≥5(∑_u ∈ T ∩ Y(6-d(u))(r_u+
                 1√(5)s_u) )^2/∑_u ∈ T ∩ Y (6-d(u))
       =    (∑_u ∈ T ∩ Y(6-d(u))(r_u+1
                √(5)s_u) )^2.
 
  Using Lemma <ref>,
  
    _K^t_u(Y)   ≥ t_u^2+2t_u√(K[Y])
       ≥15∑_u ∈ T ∩ Y(6-d(u))t_u^2+2t_u∑_u ∈ T ∩ Y(6-d(u))(r_u+1√(5)s_u) 
       =∑_u ∈ T ∩ Y(6-d(u))(15t_u^2+2r_ut_u+
            2√(5)s_ut_u),

  with equality only if t_u=0, because K is a simple triangulation of the sphere,
  and as such has no vertex of degree 1. Summing over all 5-moats gives the inequality
  
    m_5 ≥15t^2+2⟨ r,t ⟩+2√(5)⟨ s,t ⟩,

  with equality only if t=0.
  
  The moats are disjoint, so by
  inequalitites (<ref>), (<ref>) and (<ref>),
  
    K    ≥ m_1+m_3+m_5
       ≥ 5r^2 + s^2 + 15t^2 + 2√(5)⟨ r,s ⟩ +
                     2⟨ r,t ⟩ + 2√(5)⟨ s,t ⟩
       =    √(5)r + s +  1√(5)t^2.

  Hence, by the Cauchy–Schwarz inequality and (<ref>),
  
    √(15∑_u ∈ T(6-d(u))  K)   ≥√(∑_u ∈ T(6-d(u)))r +  1√(5)s +  15t
       ≥⟨ r +  1√(5) s +  15 t,1⟩
       ≥⟨ r +  13 s +  15 t,1⟩
        =    ν(K,T).

  This completes the proof of the first part of Theorem <ref>.

  To prove the inequality ν(K,T)≤√(12  K/5), it suffices
  to observe that ∑_u∈ T(6-d(u))≤ 12
  by Lemma <ref>. Now suppose that
  ν(K,T)=√(12  K/5). By Lemma <ref>, there
  exists a packing ℳ=⋃_X ∈ℱ_K^w_X(X)
  of 1-, 3- and 5-moats in K of total width √(12  K/5).
  Then ∑_u ∈ T(6-d(u))=12, i.e., all
  vertices of degree less than 6 have odd degree, namely, 3 or 5.
  Equality holds in (<ref>) and in (<ref>), so t=s=0.
  Furthermore, equality holds in (<ref>), so there is a natural
  number k ≥ 1 such that r_u=k for every u ∈ T. Therefore, every u ∈ T has
  degree 5, so |T|=12. By Lemma <ref> each moat
  _K^k(u) ∈ℳ has area 5k^2, so K=12·5 k^2=60k^2.   
  Hence, K is the union of twelve face-disjoint 1-moats ^k(u),
  for u ∈ T (see Figure <ref>). Each ^k(u) can be identified
  with a face of a regular dodecahedron, which shows that (K) contains
  a subgroup isomorphic to I_h. On the other hand, the dual graph of K is
  a fullerene graph, and it can be shown (see e.g. <cit.>) that the largest
  possible automorphism group of a fullerene graph is isomorphic to I_h. Hence,
  (K) ≅ I_h.
    
  Conversely, suppose K is a triangulation of the sphere with K=60k^2,
  all vertices of degree 5 and 6, and (K) ≅ I_h. Then it can be
  shown (see <cit.>) that K can be constructed by pasting
  triangular regions of the (infinite) 6-regular triangulation of the plane
  into the faces of a regular icosahedron (this is sometimes known in the literature
  as the Goldberg–Coxeter construction). The construction is uniquely
  determined by a 2-dimensional vector (i,j) ∈^2, known as the
  Goldberg–Coxeter vector (see Figure <ref>).
  Since (K)≅ I_h, we must have j=0 or j=i.
  The area of K is given by the formula K = 20(i^2 + ij + j^2).
  The condition K=60k^2 implies that the Goldberg–Coxeter vector of K is
  (k,k), which means that the distance between
  any pair of 5-vertices in K is at least 2k. Therefore,
  ⋃_u ∈ T^k(u) is a packing of 1-moats of total width
  12k=12√( K/60)=√(12  K/5), so ν(K,T)≥√(12  K/5).








§ PROOF OF THEOREM <REF>


Given a triangulation K of the sphere, we construct the refinement K̂
as follows. First, we subdivide each edge of K, that is, we replace it by an
internally disjoint path of length 2, and then we add three new edges inside every face,
incident to the three vertices of degree 2. (For an illustration, see Figure <ref>.)
Therefore, every face of K is divided into four faces of K̂.
Observe that all the vertices in V(K̂)∖ V(K) have degree 6 in
K̂, so if T is the set of odd-degree vertices of K, then T
is also the set of odd-degree vertices of K̂.



The following lemma was proved in <cit.> using a theorem of
Seymour <cit.>.


  If K is a triangulation of the sphere and T ⊆ V(K) is a subset
  of even cardinality, then τ(K,T)=12 ν(K̂,T).


Theorem <ref> and Lemma <ref> immediately
give the following tight upper bound on the minimum size of a postman set in a plane
triangulation with maximum degree 6.



  Let K be a triangulation of the sphere with f faces and maximum degree at most 6.
  If T is the set of odd-degree vertices of G, then
  
    τ(K,T) ≤√(15 ∑_u ∈ T(6-d(u))  K).

  In particular,
  τ(K,T) ≤√(12  K/5) always holds, with equality if and only if
  all vertices have degree 5 and 6, K=60k^2 for some k ∈, and
  (G) ≅ I_h.



  Let K be a triangulation of the sphere with maximum degree at most 6, and
  let K̂ be its refinement; observe that K̂=4  K. By
  Lemma <ref> and Theorem <ref>,
  
    τ(K,T)=12 ν(K̂,T)≤√(15∑_u∈ T(6-d(u))  K)≤√(12  K/5),

  as required.
  
  If τ(K,T)=√(12  K/5), then ν(K̂,T) = √(12· 4  K/5),
  so by the second part of Theorem <ref>, all vertices in K̂
  have degree 5 and 6, and this must clearly hold in K. Furthermore,
  4  K=60k̂^2, for some k̂∈, so K=15k̂^2.
  Since K is even, k̂=2k, for some k ∈, so K=60k^2.  
  We also have (K)≅(K̂) ≅ I_h.
  
  Conversely, suppose K is a triangulation of the sphere with K=60k^2,
  all vertices of degree 5 and 6, and (K)≅ I_h. By
  Theorem <ref> ν(K,T)=√(12  K/5), so
  τ(K,T)=√(12  K/5).


Theorem <ref> follows from Theorem <ref> by taking the planar
dual.


  Let G be a 3-connected cubic plane graph on n vertices with all faces of
  size at most 6, with p pentagonal and t triangular faces.
  By Lemma <ref>, the dual graph G^* is a plane triangulation
  with G^*=n and all vertices of degree at most 6, having exactly p vertices
  of degree 5 and t vertices of degree 3. Let T be the set of vertices
  of odd degree, J^* a minimum T-join of G^*, and J the set of edges of G
  which correspond to J^*. Since G^*∖ J^* has no odd-degree vertices,
  G∖ J=(G^*∖ J^*)^* has no odd faces, so is bipartite. By Theorem <ref>,
  
    |J|=|J^*| ≤√(15∑_u∈ T(6-d(u))n) = √(15(p+3t)n).

  In particular, |J|≤√(12n/5), with equality if and only if all faces
  have size 5 and 6, n=60k^2 for some k ∈, and (G) ≅ I_h.




§ CONSEQUENCES FOR MAX-CUT AND INDEPENDENCE NUMBER


A classic problem in combinatorial optimisation, known as max-cut,
asks for the maximum size of an edge-cut in a given graph. This problem is
known to be NP-hard, even when restricted to triangle-free cubic graphs <cit.>.
However, for the class of planar graphs, the problem
can be solved in polynomial time using standard tools from combinatorial
optimisation (namely T-joins), as observed by Hadlock <cit.>.
Cui and Wang <cit.> proved that every planar, cubic graph on
n vertices has a cut of size at least 39n/32-9/16, improving an earlier
bound of Thomassen <cit.>. However, when the face size is bounded by
6, we get the following improved bound.



  If G is a 3-connected cubic plane graph on n vertices with all faces of size at
  most 6, with p pentagonal and t triangular faces, then G has a
  cut of size at least
  
    3n/2-√((p+3t)n/5).

  In particular, G has a cut of size at least 3n/2-√(12n/5), with
  equality if and only if all faces have size 5 and 6, n=60k^2 for some
  k ∈, and (G) ≅ I_h.



  Let G be a 3-connected cubic plane graph on n vertices with all faces
  of size at most 6. Let J ⊆ E(G) be an odd cycle transversal, and
  let X be a colour class of G∖ J. Then
  |δ_G(X)| = 3n/2-|J|. By Theorem <ref>, we can always find J
  such that |J|≤√(12n/5), with equality if and only if all faces have
  size 5 and 6, n=60k^2 for some k ∈, and (G) ≅ I_h.


A set of vertices in a graph is independent if there is no edge between
any of its vertices, and the maximum size of an independent set in G is the
independence number α(G). Heckman and Thomas <cit.> showed
that every triangle-free, cubic, planar graph has an independent set of size at
least 3n/8, and this bound is tight. Again, forbidding faces of size greater
than 6 gives a much better bound.



  If G is a 3-connected cubic plane graph on n vertices with all faces of size at
  most 6, with p pentagonal and t triangular faces, then
  
    α(G) ≥ n/2-√((p+3t)n/20).

  In particular, α(G) ≥ n/2-√(3n/5), with equality
  if and only if all faces have size 5 and 6, n=60k^2 for some
  k ∈, and (G) ≅ I_h.



  Every graph G contains an odd cycle vertex transversal U such that
  |U| ≤τ_(G), so
  α(G) ≥α(G∖ U) ≥ n/2-τ_(G)/2. Therefore, by
  Theorem <ref>, α(G) ≥ n/2-√(3n/5), for every 3-connected
  cubic graph G with all faces of size at most 6. When J^* is
  a minimum T-join of G^*, every face of G^* is incident to at most one edge
  of J^*. This means that the set J ⊂ E(G) corresponding to J^* is a
  matching of G. Therefore, by Theorem <ref>, equality holds if and only
  if all faces have size 5 and 6, n=60k^2 for some k ∈, and
  (G) ≅ I_h.




§ CONCLUDING REMARKS


Clearly, a necessary condition for τ_=O(√(n)) is that
ν_=O(√(n)). In the case of planar graphs, the theorem of
Král' and Voss <cit.> mentioned
in the introduction guarantees that it is also a sufficient condition.
It can be shown that ν_=O(√(n)) is also a
necessary and sufficient condition for having a max-cut of size at least
3n/2-O(√(n)), and for having an independent set of size at least n/2-O(√(n)).

It is not hard to construct an infinite
family of 3-connected cubic plane graphs with all faces of size at most 7
such that τ_≥ε n, for a constant ε > 0.
This shows that the condition on the size of faces in Theorem <ref> and
Corollaries <ref> and <ref> cannot be relaxed.

To construct such a family, consider the graphs C and R in
Figure <ref>. Note that C is embedded in a disc, and R is embedded
in a cylinder. There are ten vertices on the boundary of C and also on each boundary
of R, with the degree alternating between 2 and 3. We can paste k copies of
R along their boundaries, and then paste a copy of C on each boundary of the
resulting cylinder. Assuming k>0, this gives a 3-connected cubic plane graph G on
n=15+40k vertices with all faces of size 5 and 7, such that
ν_(G) ≥ 4+5k>18n.



Finally, we remark that bounding τ_ is much simpler if the graph contains no
pentagonal faces. In this case, the bound in Theorem <ref> can be improved to
τ_(G) ≤√(tn/3), where t is the number of triangular
faces. In particular, τ_(G) ≤√(4n/3), with equality if and only if
all faces have size 3 and 6, n=12k^2 for some k ∈, and
(G) ≅ T_d. Corollaries <ref> and <ref>
can be strengthened in the same way.

plain


