On the max‐cut problem for a planar,cubic, triangle‐free graph,and the Chinese postman problem for a planar triangulation

Every 3‐connected planar, cubic, triangle‐free graph with n vertices has a bipartite subgraph with at least 29n/24 ? 7/6 edges. The constant 29/24 improves the previously best known constant 6/5 which was considered best possible because of the graph of the dodecahedron. Examples show that the constant 29/24 = 1.2083… cannot be raised to more than 47/38 = 1.2368…. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 261–269, 2006