Degree-pattern classification at total cubic deficiency five
ProvedCubicP3Partition.q5_subcubic_degree_patterncombinatoricscubic-graphsdegree-sequencegraph-theory
Let be a finite graph in which every vertex has degree one, two, or three. Suppose the total deficiency from cubicity is five:
If and denote the numbers of degree-one and degree-two vertices, then , and necessarily
This elementary classification is useful for organizing five-port residual configurations.
Preamble
import Mathlib import Definitions.Def_cubic_p3_partition_models
Formal statement
namespace CubicP3Partition
/-- A finite subcubic graph of minimum degree one and total cubic deficiency five has degree-one/degree-two counts (0,5), (1,3), or (2,1). -/
theorem q5_subcubic_degree_pattern
{V : Type} [Fintype V] [DecidableEq V]
{G : SimpleGraph V}
(hdeg : ∀ v, 1 ≤ degree G v ∧ degree G v ≤ 3)
(hdef : ∑ v, (3 - degree G v) = 5) :
2 * (Finset.filter (fun v => degree G v = 1) Finset.univ).card +
(Finset.filter (fun v => degree G v = 2) Finset.univ).card = 5 ∧
((Finset.filter (fun v => degree G v = 1) Finset.univ).card = 0 ∧
(Finset.filter (fun v => degree G v = 2) Finset.univ).card = 5 ∨
(Finset.filter (fun v => degree G v = 1) Finset.univ).card = 1 ∧
(Finset.filter (fun v => degree G v = 2) Finset.univ).card = 3 ∨
(Finset.filter (fun v => degree G v = 1) Finset.univ).card = 2 ∧
(Finset.filter (fun v => degree G v = 2) Finset.univ).card = 1) := 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: A. Kelmans, ‘Packing 3-vertex paths in cubic 3-connected graphs’, arXiv:0801.1239.