An Approach to the Girth Problem in Cubic Graphs

ABSTRACT We offer a new, gradual approach to the largest girth problem for cubic graphs . It is easily observed that the largest possible girth of all ‐vertex cubic graphs is attained by a 2‐connected graph . By Petersen's graph theorem, is the disjoint union of a 2‐factor and a perfect matching . We refer to the edges of as ribs and classify the cycles in by their number of ribs. We define to be the smallest integer such that every cubic ‐vertex graph with a given perfect matching has a cycle of length at most with at most ribs. Here, we determine this function up to small additive constant for and up to a small multiplicative constant for larger .