P3-factors are equivalent to duplicated-center Hall systems
ProvedCubicP3Partition.p3Factor_iff_center_hallcombinatoricsgraph-theoryhall-theoremp3-factor
Let be a finite simple graph. Then has a spanning non-induced -factor if and only if there is a set with such that every subset has at least neighbours outside :
The equivalence turns a -factor into its set of middle vertices and, conversely, realizes two leaf slots per center through Hall's theorem. It gives an exact finite matching characterization and does not assume cubicity or connectivity.
Formalization Note The predicate p12CenterHall is the two-fold Hall condition on duplicated center slots.
Preamble
import Definitions.Def_cubic_p3_partition_models import Definitions.Def_cubic_p3_partition_center_hall
Formal statement
namespace CubicP3Partition
universe u
/-- Exact characterization of finite non-induced P3-factors by a one-third-size center set satisfying the duplicated-center Hall inequalities. -/
theorem p3Factor_iff_center_hall
{V : Type u} [Fintype V] {G : SimpleGraph V} :
Nonempty (P3Factor G) ↔
∃ C : Finset V, p12CenterSize C ∧ p12CenterHall G C := by sorry
end CubicP3PartitionSource
Derived structural theorem for the Prove2me mission ‘P3-Partitions of Cubic 3-Connected Graphs (OPG-46613)’, https://prove2.me/missions/P3-Partitions%20of%20Cubic%203-Connected%20Graphs%20%28OPG-46613%29; the exact Hall characterization is a project-derived auxiliary theorem.