Triangle deletion in a divisible-order cubic 3-connected graph leaves a 2-connected residual
ProvedCubicP3Partition.cubic_triangle_residual_two_connectedconnectivitycubic-graphsgraph-theorytriangles
Let be a finite cubic three-vertex-connected graph whose order is divisible by three, and let be a triangle. After deleting , the induced residual graph is connected. Moreover, deleting any one additional residual vertex still leaves it connected. Thus the triangle residual has no cut vertex in the explicit deletion-connectivity sense used here.
The theorem is a structural reduction for studying -factors; it does not itself construct such a factor.
Preamble
import Mathlib import Definitions.Def_cubic_p3_partition_models
Formal statement
namespace CubicP3Partition
/-- In a finite cubic three-vertex-connected graph of order divisible by three, deleting a triangle leaves a connected residual with no cut vertex. -/
theorem cubic_triangle_residual_two_connected
{V : Type} [Fintype V] [DecidableEq V]
{G : SimpleGraph V} [DecidableRel G.Adj]
(hC : Cubic G) (h3 : ThreeVertexConnected G)
(hdiv : 3 ∣ Fintype.card V)
{a b c : V}
(hab : G.Adj a b) (hbc : G.Adj b c) (hca : G.Adj c a) :
(G.induce {v : V | v ≠ a ∧ v ≠ b ∧ v ≠ c}).Connected ∧
∀ x : V, x ≠ a ∧ x ≠ b ∧ x ≠ c →
(G.induce {v : V | v ≠ a ∧ v ≠ b ∧ v ≠ c ∧ v ≠ x}).Connected := 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.