Short-Cycle Decompositions and Full Zombie Damage in Cubic Graphs

Abstract

Every connected union H of triangles and quadrilaterals with minimum degree two and maximum degree three has at most four degree-two vertices, called ports. We classify these unions when the number of ports is zero or at least two, including the known closed cubic families. Explicit local strategies and an interface-composition theorem yield a characterization of full zombie damage in finite, simple, connected, bridgeless cubic graphs: the only exceptions are K₄, K₃,₃, the triangular prism, and the cube. This proves Conjecture 24 of Davila. In every positive case the survivor can force full damage within 2n(n + 1) moves, against every choice among geodesic zombie replies. If the graph has an edge on neither a triangle nor a quadrilateral, the survivor can safely depart from every vertex infinitely often. Five finite routing components are supported by complete ranked policies with 19 representative tasks and 121 states. An end-to-end Lean 4.32.0 formalization proves the universal classification, four-port bound, full-damage characterization and recurrent coverage, including the construction of the component models, routing strategies and initial placement from the graph hypotheses.