has_induced_k4_subdivision
A graph G contains an induced subdivision of K4: there are four distinct branch vertices and one simple path for each of their six unordered pairs. No branch vertex is internal to a path; distinct paths share only branch vertices; and every G-edge between vertices of their union is an edge of one of the paths.
Statement
def has_induced_k4_subdivision {V : Type*} (G : SimpleGraph V) : Prop
- Defined in
- arXiv:2610.32404, definition of ISK4-freeness and Lemma 11.1. The standard induced subdivision is encoded by six paths with disjoint interiors whose union is induced.
- Verified
- 27 Oct 2026
- Axioms
- none listed
- Used by 4
- k4_claw_diamond_free_has_no_induced_k4_subdivisionEvery simple graph containing neither an induced K4, an induced claw, nor an induced diamond contains no induced subdivision of K4.
- subdivided_k33_line_graph_isk4_diamond_free_four_chromaticLet H be the graph obtained from K3,3 by subdividing one edge exactly once, and let G be its line graph. Then G has no induced subdivision…
- not_has_induced_k4_subdivision_botThe empty graph on any vertex type contains no induced subdivision of K4.
- has_induced_k4_subdivision_topThe complete graph on four vertices contains an induced subdivision of K4, using the six single-edge paths.
Read back from the Lean
For a simple graph $G$ with vertex type $V$, has_induced_k4_subdivision G asserts that $G$ contains an induced subdivision of $K_4$. Specifically, there exist:
1. An injective map $b : \mathrm{Fin}\ 4 \to V$ (the four branch vertices), and
2. A family of walks $P$ indexed by pairs $e = (i, j) \in \mathrm{Fin}\ 4 \times \mathrm{Fin}\ 4$ with $i < j$, such that each $P(e)$ is a walk in $G$ from $b(i)$ to $b(j)$,
satisfying:
- Each walk $P(e)$ is a path (contains no repeated vertices).
- For every pair $e$ and index $i \in \mathrm{Fin}\ 4$, if the branch vertex $b(i)$ belongs to the support (vertex set) of $P(e)$, then $i$ is an endpoint of $e$ (i.e., $i = e.1$ or $i = e.2$).
- For any two distinct pairs $e \neq f$ and any vertex $v \in V$, if $v$ is in the support of $P(e)$ and in the support of $P(f)$, then $v$ is a branch vertex (there exists $i \in \mathrm{Fin}\ 4$ such that $v = b(i)$).
- For any vertices $x, y \in V$, if $x$ belongs to the support of some path $P(e)$ and $y$ belongs to the support of some path $P(e')$, and $x$ and $y$ are adjacent in $G$, then the undirected edge $s(x, y)$ belongs to the edge set of some path $P(e'')$ (i.e., the subgraph induced by the vertices of the subdivision has no edges other than those of the paths).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- Contains an induced subdivision of K4, encoded by six internally disjoint simple paths between four distinct branch vertices, with no extra edges on their union. -/ def has_induced_k4_subdivision {V : Type*} (G : SimpleGraph V) : Prop := ∃ (b : Fin 4 → V), Function.Injective b ∧ ∃ (P : (e : {ij : Fin 4 × Fin 4 // ij.1 < ij.2}) → G.Walk (b e.val.1) (b e.val.2)), (∀ e, (P e).IsPath) ∧ (∀ e i, b i ∈ (P e).support → i = e.val.1 ∨ i = e.val.2) ∧ (∀ e f, e ≠ f → ∀ v, v ∈ (P e).support → v ∈ (P f).support → ∃ i, v = b i) ∧ (∀ x y, (∃ e, x ∈ (P e).support) → (∃ e, y ∈ (P e).support) → G.Adj x y → ∃ e, s(x, y) ∈ (P e).edges)