A minimum-change version of the Chung–Feller theorem for Dyck paths.

A Dyck path of length 2 k with e flaws is a path in the integer lattice that starts at the origin and consists of k many ↗ -steps and k many ↘ -steps that change the current coordinate by ( 1 , 1 ) or ( 1 , − 1 ) , respectively, and that has exactly e many ↘ -steps below the line y = 0 . Denoting by D 2 k e the set of Dyck paths of length 2 k with e flaws, the well-known Chung–Feller theorem asserts that the sets D 2 k 0 , D 2 k 1 , … , D 2 k k all have the same cardinality 1 k + 1 2 k k = C k , the k th Catalan number. The standard combinatorial proof of this classical result establishes a bijection f ′ between D 2 k e and D 2 k e + 1 that swaps certain parts of the given Dyck path x , with the effect that x and f ′ ( x ) may differ in many positions. In this paper we strengthen the Chung–Feller theorem by presenting a simple bijection f between D 2 k e and D 2 k e + 1 which has the additional feature that x and f ( x ) differ in only two positions (the least possible number). We also present an algorithm that allows to compute a sequence of applications of f in constant time per generated Dyck path. As an application, we use our minimum-change bijection f to construct cycle-factors in the odd graph O 2 k + 1 and the middle levels graph M 2 k + 1 – two intensively studied families of vertex-transitive graphs – that consist of C k many cycles of the same length. [ABSTRACT FROM AUTHOR]