Three one-residue cycles with adjacent cross edges have a P3-factor
ProvedCubicP3Partition.R03SP01ThreeOneAdjacentCenterOfTwoFactorcombinatoricsgraph-theoryp3-factortwo-factor
Let be a finite simple graph and let be a spanning -factor of . Suppose the vertex set is partitioned into three cyclically ordered parts , , and , each of size congruent to modulo , and every successor edge in each cyclic order belongs to . Assume the first part has at least four vertices. If the first two consecutive vertices of are respectively adjacent in to distinguished vertices of and , then has a spanning -factor.
This is a conditional assembly lemma for combining three one-residue cycles. It does not assert that every graph in OPG-46613 admits the required cyclic decomposition or cross edges.
Preamble
import Definitions.Def_cubic_p3_partition_models
Formal statement
namespace CubicP3Partition
universe u
theorem R03SP01ThreeOneAdjacentCenterOfTwoFactor
{V : Type u} [Fintype V]
(G F : SimpleGraph V)
(hTF : TwoFactor G F)
{A B C : Type u} [Fintype A] [Fintype B] [Fintype C]
(eV : A ⊕ (B ⊕ C) ≃ V)
(kA kB kC : Nat)
(eA : Fin (1 + kA * 3) ≃ A)
(eB : Fin (1 + kB * 3) ≃ B)
(eC : Fin (1 + kC * 3) ≃ C)
(cycleA : ∀ i : Fin (1 + kA * 3),
F.Adj (eV (Sum.inl (eA i)))
(eV (Sum.inl (eA ⟨(i.val + 1) % (1 + kA * 3), Nat.mod_lt _ (by omega)⟩))))
(cycleB : ∀ i : Fin (1 + kB * 3),
F.Adj (eV (Sum.inr (Sum.inl (eB i))))
(eV (Sum.inr (Sum.inl (eB ⟨(i.val + 1) % (1 + kB * 3), Nat.mod_lt _ (by omega)⟩)))))
(cycleC : ∀ i : Fin (1 + kC * 3),
F.Adj (eV (Sum.inr (Sum.inr (eC i))))
(eV (Sum.inr (Sum.inr (eC ⟨(i.val + 1) % (1 + kC * 3), Nat.mod_lt _ (by omega)⟩)))))
(hkA : 0 < kA)
(hcrossAB : G.Adj (eV (Sum.inl (eA ⟨0, by omega⟩)))
(eV (Sum.inr (Sum.inl (eB ⟨0, by omega⟩)))))
(hcrossAC : G.Adj (eV (Sum.inl (eA ⟨1, by omega⟩)))
(eV (Sum.inr (Sum.inr (eC ⟨0, by omega⟩))))) :
Nonempty (P3Factor G) := by sorry
end CubicP3PartitionSource
Derived auxiliary 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; background source: A. Kelmans, “Packing 3-vertex paths in cubic 3-connected graphs”, arXiv:0801.1239. The exact conditional three-cycle assembly is not asserted as a theorem in the cited source.