subdivided_k33_line_graph_no_k4_claw_diamond
The line graph of the once-subdivided K3,3 has no induced K4, claw, or diamond.
Statement
theorem subdivided_k33_line_graph_no_k4_claw_diamond :
(¬ SimpleGraph.IsIndContained (⊤ : SimpleGraph (Fin 4)) h_subdivided_k33.lineGraph) ∧
IsClawFree h_subdivided_k33.lineGraph ∧ is_diamond_free h_subdivided_k33.lineGraph- Source
- Helper for arXiv:2610.32404 Proposition 11.2 (PR-412).
- Verified
- 31 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- h_subdivided_k33The 7-vertex graph obtained by subdividing one edge of the complete bipartite graph K_{3,3} exactly once.
- IsClawFreeA simple graph G is claw-free if it does not contain the complete bipartite graph K_{1,3} as an induced subgraph.
- is_diamond_freeA simple graph G is diamond-free if it does not contain the diamond graph as an induced subgraph.
- diamond_graphThe diamond graph is the simple graph on vertex type Fin 4 obtained from the complete graph ⊤ by deleting the single edge between vertex 0…
- Used by 1
- 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…
The proof, explained
The theorem is proved by first establishing general combinatorial lemmas about line graphs of triangle-free graphs with maximum degree at most 3. First, any three pairwise intersecting edges in a triangle-free graph must share a single common vertex; consequently, four distinct edges cannot contain two overlapping triangles in the line graph without creating a vertex of degree at least 4. Second, no edge in a line graph can intersect three mutually disjoint edges because an edge has only two endpoints (by the pigeonhole principle). Finally, exhaustive finite computation verifies that the once-subdivided K3,3 is triangle-free and has maximum degree 3, ruling out an induced K4, diamond, and claw in its line graph.
If any two of the intersection witnesses p ∈ e₁ ∩ e₂, q ∈ e₁ ∩ e₃, and r ∈ e₂ ∩ e₃ coincide, then all three edges share a common vertex.
Let p, q, and r be vertices shared by the pairs (e₁, e₂), (e₁, e₃), and (e₂, e₃) respectively. We perform case analysis on whether any two of these vertices are identical. If p = q, then p belongs to e₁, e₂, and e₃ simultaneously. The cases p = r and q = r similarly show that p or q is common to all three edges.
obtain ⟨p, p1, p2⟩ := a12 obtain ⟨q, q1, q3⟩ := a13 obtain ⟨r, r2, r3⟩ := a23 by_cases hpq : p = q · subst hpq; exact ⟨p, p1, p2, q3⟩ by_cases hpr : p = r · subst hpr; exact ⟨p, p1, p2, r3⟩ by_cases hqr : q = r · subst hqr; exact ⟨q, q1, r2, q3⟩
The intersection witnesses p, q, r cannot be pairwise distinct in a triangle-free graph, completing the proof of `sk33_line_common_vertex`.
Assuming p, q, r are pairwise distinct, the edge e₁ contains the two distinct vertices p and q, so e₁ = {p, q} by `Sym2.mem_and_mem_iff`. Similarly, e₂ = {p, r} and e₃ = {q, r}. These three edges would form a triangle p-q-r in H, contradicting the hypothesis `htri` that H contains no triangles.
uses
Sym2.mem_and_mem_iff,SimpleGraph.mem_edgeSetexfalso have E1 : e1 = s(p, q) := (Sym2.mem_and_mem_iff hpq).1 ⟨p1, q1⟩ have E2 : e2 = s(p, r) := (Sym2.mem_and_mem_iff hpr).1 ⟨p2, r2⟩ have E3 : e3 = s(q, r) := (Sym2.mem_and_mem_iff hqr).1 ⟨q3, r3⟩ subst E1 E2 E3 exact htri p q r ((SimpleGraph.mem_edgeSet H).1 h1) ((SimpleGraph.mem_edgeSet H).1 h3) ((SimpleGraph.mem_edgeSet H).1 h2)
Four distinct edges e₁, e₂, e₃, e₄ with e₁, e₂, e₃ and e₂, e₃, e₄ pairwise intersecting must all share a single common vertex x.
Applying `sk33_line_common_vertex` to e₁, e₂, e₃ yields a common vertex x ∈ e₁ ∩ e₂ ∩ e₃, and applying it to e₂, e₃, e₄ yields a common vertex y ∈ e₂ ∩ e₃ ∩ e₄. If x ≠ y, then both e₂ and e₃ contain the distinct pair {x, y}, forcing e₂ = e₃, which contradicts e₂ ≠ e₃. Thus x = y, so all four edges pass through x.
uses
sk33_line_common_vertex,Sym2.mem_and_mem_iffobtain ⟨x, x1, x2, x3⟩ := sk33_line_common_vertex H htri e1 e2 e3 h1 h2 h3 a12 a13 a23 obtain ⟨y, y2, y3, y4⟩ := sk33_line_common_vertex H htri e2 e3 e4 h2 h3 h4 a23 a24 a34 have hxy : x = y := by by_contra h exact n23 (((Sym2.mem_and_mem_iff h).1 ⟨x2, y2⟩).trans ((Sym2.mem_and_mem_iff h).1 ⟨x3, y3⟩).symm) subst hxy
The four distinct edges incident to x contradict the maximum degree bound of H, proving `sk33_line_no_four`.
Since all four edges contain x, they can be written as {x, a}, {x, b}, {x, c}, and {x, d} for some neighbors a, b, c, d of x. The hypothesis `hdeg` asserts that at least two of these four neighbors must coincide. Equating any two of them makes two of the edges identical, contradicting the assumption that all four edges are distinct.
uses
SimpleGraph.mem_edgeSetobtain ⟨a, rfl⟩ := Sym2.mem_iff_exists.1 x1 obtain ⟨b, rfl⟩ := Sym2.mem_iff_exists.1 x2 obtain ⟨c, rfl⟩ := Sym2.mem_iff_exists.1 x3 obtain ⟨d, rfl⟩ := Sym2.mem_iff_exists.1 y4 rw [SimpleGraph.mem_edgeSet] at h1 h2 h3 h4 rcases hdeg x a b c d h1 h2 h3 h4 with rfl | rfl | rfl | rfl | rfl | rfl <;> simp_all
An edge e₀ cannot intersect three pairwise disjoint edges f₁, f₂, f₃, proving `sk33_line_no_claw`.
Writing the central edge as e₀ = {a, b} using `Sym2.ind`, each edge fᵢ meets e₀ at a vertex vᵢ ∈ {a, b}. By case analysis on whether each vᵢ is a or b, the pigeonhole principle implies that at least two of the three vertices must be identical. Thus two of the edges f₁, f₂, f₃ share an endpoint, contradicting the assumption that they are mutually disjoint.
uses
Sym2.ind,Sym2.mem_iffinduction e0 using Sym2.ind with | h a b => obtain ⟨v1, hv1, w1⟩ := a1 obtain ⟨v2, hv2, w2⟩ := a2 obtain ⟨v3, hv3, w3⟩ := a3 rw [Sym2.mem_iff] at hv1 hv2 hv3 rcases hv1 with e1 | e1 <;> rcases hv2 with e2 | e2 <;> rcases hv3 with e3 | e3 <;> subst e1 e2 e3 <;> first | exact b12 ⟨_, w1, w2⟩ | exact b13 ⟨_, w1, w3⟩ | exact b23 ⟨_, w2, w3⟩
Adjacency in `h_subdivided_k33` is equivalent to the boolean decision function `sk33_adjB`. automation
Exhaustive finite case analysis over all pairs of vertices in `Fin 7` using `fin_cases` verifies that the relational definition of `h_subdivided_k33` matches the boolean function `sk33_adjB`.
fin_cases x <;> fin_cases y <;> simp [h_subdivided_k33, sk33_adjB]The graph `h_subdivided_k33` contains no triangles (`sk33_tri`). automation
Rewriting graph adjacency to the boolean function `sk33_adjB` via `sk33_adj_iff`, Lean's `decide` tactic evaluates all triples in `Fin 7` and confirms that no three mutually adjacent vertices exist.
uses
sk33_adj_iffsimp only [sk33_adj_iff]; decide
Every vertex in `h_subdivided_k33` has at most 3 distinct neighbors (`sk33_deg`). automation
Rewriting graph adjacency via `sk33_adj_iff`, Lean's `decide` tactic checks all 5-tuples in `Fin 7` and confirms that among any four neighbors of a vertex, at least two must be equal.
uses
sk33_adj_iffsimp only [sk33_adj_iff]; decide
An induced subgraph embedding into the line graph maps adjacent vertices to distinct edges of H that share an incident vertex.
For any induced embedding f : K ↪g L(H) and adjacent vertices i ∼ j in K, the image vertices f(i) and f(j) are adjacent in L(H). By `SimpleGraph.lineGraph_adj_iff_exists`, this means f(i) and f(j) are distinct edges of H that share at least one vertex.
uses
SimpleGraph.lineGraph_adj_iff_exists,Subtype.exthave adj : ∀ {W : Type} (K : SimpleGraph W) (f : K ↪g h_subdivided_k33.lineGraph) (i j : W), K.Adj i j → (f i : Sym2 (Fin 7)) ≠ f j ∧ ∃ v, v ∈ (f i : Sym2 (Fin 7)) ∧ v ∈ (f j : Sym2 (Fin 7)) := by intro W K f i j h have := f.map_rel_iff.2 h rw [SimpleGraph.lineGraph_adj_iff_exists] at this exact ⟨fun e => this.1 (Subtype.ext e), this.2⟩
The line graph of `h_subdivided_k33` contains no induced K₄.
We split the theorem into its three conjuncts. If there were an induced embedding f of K₄ into the line graph, the four image edges would be pairwise distinct and pairwise intersecting. Applying `sk33_line_no_four` together with the triangle-freeness (`sk33_tri`) and degree bound (`sk33_deg`) of the subdivided graph immediately yields a contradiction.
uses
sk33_line_no_four,sk33_tri,sk33_degrefine ⟨?_, ?_, ?_⟩ · rintro ⟨f⟩ have A : ∀ i j : Fin 4, i ≠ j → (f i : Sym2 (Fin 7)) ≠ f j ∧ ∃ v, v ∈ (f i : Sym2 (Fin 7)) ∧ v ∈ (f j : Sym2 (Fin 7)) := fun i j h => adj _ f i j h exact sk33_line_no_four _ sk33_tri sk33_deg _ _ _ _ (f 0).2 (f 1).2 (f 2).2 (f 3).2 (A 0 1 (by decide)).1 (A 0 2 (by decide)).1 (A 0 3 (by decide)).1 (A 1 2 (by decide)).1 (A 1 3 (by decide)).1 (A 2 3 (by decide)).1 (A 0 1 (by decide)).2 (A 0 2 (by decide)).2 (A 1 2 (by decide)).2 (A 1 3 (by decide)).2 (A 2 3 (by decide)).2
The line graph of `h_subdivided_k33` is claw-free.
Suppose f embeds the claw K₁,₃ into the line graph, with center inl 0 and leaves inr 0, inr 1, inr 2. The central edge f(inl 0) intersects each leaf edge f(inr j). Because no two leaves are adjacent in K₁,₃ and f is an induced embedding, no two leaf edges can share a vertex (as that would make them adjacent in the line graph). The three leaf edges are therefore pairwise disjoint, contradicting `sk33_line_no_claw`.
uses
SimpleGraph.lineGraph_adj_iff_exists,sk33_line_no_claw· rintro ⟨f⟩ have A : ∀ j : Fin 3, ∃ v, v ∈ (f (Sum.inl 0) : Sym2 (Fin 7)) ∧ v ∈ (f (Sum.inr j) : Sym2 (Fin 7)) := fun j => (adj _ f (Sum.inl 0) (Sum.inr j) (by simp)).2 have B : ∀ i j : Fin 3, i ≠ j → ¬ ∃ v, v ∈ (f (Sum.inr i) : Sym2 (Fin 7)) ∧ v ∈ (f (Sum.inr j) : Sym2 (Fin 7)) := by intro i j hij hv have hne : f (Sum.inr i) ≠ f (Sum.inr j) := fun e => hij (by simpa using f.injective e) have : h_subdivided_k33.lineGraph.Adj (f (Sum.inr i)) (f (Sum.inr j)) := by rw [SimpleGraph.lineGraph_adj_iff_exists] exact ⟨hne, hv⟩ rw [f.map_rel_iff] at this simp at this exact sk33_line_no_claw _ _ _ _ (A 0) (A 1) (A 2) (B 0 1 (by decide)) (B 0 2 (by decide)) (B 1 2 (by decide))The line graph of `h_subdivided_k33` is diamond-free.
Suppose f embeds the diamond graph into the line graph, with non-edge between 0 and 3. The four edges f(0), f(1), f(2), f(3) are distinct, edges f(0), f(1), f(2) pairwise intersect (forming a triangle), and f(3) intersects both f(1) and f(2). This is the exact configuration ruled out by `sk33_line_no_four` (using `sk33_tri` and `sk33_deg`), completing the proof.
uses
Subtype.ext,sk33_line_no_four,sk33_tri,sk33_deg· rintro ⟨f⟩ have A : ∀ i j : Fin 4, diamond_graph.Adj i j → (f i : Sym2 (Fin 7)) ≠ f j ∧ ∃ v, v ∈ (f i : Sym2 (Fin 7)) ∧ v ∈ (f j : Sym2 (Fin 7)) := fun i j h => adj _ f i j h have n03 : (f 0 : Sym2 (Fin 7)) ≠ f 3 := fun e => absurd (f.injective (Subtype.ext e)) (by decide) exact sk33_line_no_four _ sk33_tri sk33_deg _ _ _ _ (f 0).2 (f 1).2 (f 2).2 (f 3).2 (A 0 1 (by simp [diamond_graph])).1 (A 0 2 (by simp [diamond_graph])).1 n03 (A 1 2 (by simp [diamond_graph])).1 (A 1 3 (by simp [diamond_graph])).1 (A 2 3 (by simp [diamond_graph])).1 (A 0 1 (by simp [diamond_graph])).2 (A 0 2 (by simp [diamond_graph])).2 (A 1 2 (by simp [diamond_graph])).2 (A 1 3 (by simp [diamond_graph])).2 (A 2 3 (by simp [diamond_graph])).2
sk33_line_common_vertex- In a triangle-free graph, if three edges pairwise intersect, then all three edges share a common vertex.
Sym2.mem_and_mem_iff- If x ≠ y, an unordered pair z contains both x and y if and only if z = {x, y}.
SimpleGraph.mem_edgeSet- An unordered pair {v, w} belongs to the edge set of G if and only if v and w are adjacent in G.
sk33_line_no_four- In a triangle-free graph with maximum degree at most 3, four distinct edges cannot contain two overlapping triangles in the line graph (i.e. e₁, e₂, e₃ pairwise intersect and e₄ intersects e₂ and e₃).
sk33_line_no_claw- In the line graph of any graph, no edge can intersect three pairwise disjoint edges.
Sym2.ind- To prove a property for all unordered pairs, it suffices to prove it for pairs of the form {x, y}.
Sym2.mem_iff- An element a belongs to {b, c} if and only if a = b or a = c.
sk33_adj_iff- Two vertices x and y in the once-subdivided K3,3 graph are adjacent if and only if the boolean function `sk33_adjB x y` returns true.
sk33_tri- The once-subdivided K3,3 graph contains no triangles.
sk33_deg- Every vertex in the once-subdivided K3,3 graph has at most 3 distinct neighbors.
SimpleGraph.lineGraph_adj_iff_exists- Two vertices in the line graph of G (edges of G) are adjacent if and only if they are distinct and share at least one vertex.
Subtype.ext- Two subtype elements are equal if their underlying values are equal.
- The absence of triangles and the maximum degree bound (at most 3) on the 7-vertex graph are verified by computational exhaustiveness (`decide` on boolean adjacency checks) rather than paper-and-pencil cycle analysis of subdivided bipartite graphs.
- An induced subgraph embedding into the line graph maps vertices to subtype elements representing edges of the underlying graph; showing that adjacent vertices in the embedding correspond to distinct edges that share a vertex requires translating between graph embeddings and line graph edge adjacency via `SimpleGraph.lineGraph_adj_iff_exists`.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem sk33_line_common_vertex {V : Type*} (H : SimpleGraph V) (htri : ∀ x y z, H.Adj x y → H.Adj y z → H.Adj x z → False) (e1 e2 e3 : Sym2 V) (h1 : e1 ∈ H.edgeSet) (h2 : e2 ∈ H.edgeSet) (h3 : e3 ∈ H.edgeSet) (a12 : ∃ v, v ∈ e1 ∧ v ∈ e2) (a13 : ∃ v, v ∈ e1 ∧ v ∈ e3) (a23 : ∃ v, v ∈ e2 ∧ v ∈ e3) : ∃ x, x ∈ e1 ∧ x ∈ e2 ∧ x ∈ e3 := by obtain ⟨p, p1, p2⟩ := a12 obtain ⟨q, q1, q3⟩ := a13 obtain ⟨r, r2, r3⟩ := a23 by_cases hpq : p = q · subst hpq; exact ⟨p, p1, p2, q3⟩ by_cases hpr : p = r · subst hpr; exact ⟨p, p1, p2, r3⟩ by_cases hqr : q = r · subst hqr; exact ⟨q, q1, r2, q3⟩ exfalso have E1 : e1 = s(p, q) := (Sym2.mem_and_mem_iff hpq).1 ⟨p1, q1⟩ have E2 : e2 = s(p, r) := (Sym2.mem_and_mem_iff hpr).1 ⟨p2, r2⟩ have E3 : e3 = s(q, r) := (Sym2.mem_and_mem_iff hqr).1 ⟨q3, r3⟩ subst E1 E2 E3 exact htri p q r ((SimpleGraph.mem_edgeSet H).1 h1) ((SimpleGraph.mem_edgeSet H).1 h3) ((SimpleGraph.mem_edgeSet H).1 h2)theorem sk33_line_no_four {V : Type*} (H : SimpleGraph V) (htri : ∀ x y z, H.Adj x y → H.Adj y z → H.Adj x z → False) (hdeg : ∀ x a b c d, H.Adj x a → H.Adj x b → H.Adj x c → H.Adj x d → a = b ∨ a = c ∨ a = d ∨ b = c ∨ b = d ∨ c = d) (e1 e2 e3 e4 : Sym2 V) (h1 : e1 ∈ H.edgeSet) (h2 : e2 ∈ H.edgeSet) (h3 : e3 ∈ H.edgeSet) (h4 : e4 ∈ H.edgeSet) (n12 : e1 ≠ e2) (n13 : e1 ≠ e3) (n14 : e1 ≠ e4) (n23 : e2 ≠ e3) (n24 : e2 ≠ e4) (n34 : e3 ≠ e4) (a12 : ∃ v, v ∈ e1 ∧ v ∈ e2) (a13 : ∃ v, v ∈ e1 ∧ v ∈ e3) (a23 : ∃ v, v ∈ e2 ∧ v ∈ e3) (a24 : ∃ v, v ∈ e2 ∧ v ∈ e4) (a34 : ∃ v, v ∈ e3 ∧ v ∈ e4) : False := by obtain ⟨x, x1, x2, x3⟩ := sk33_line_common_vertex H htri e1 e2 e3 h1 h2 h3 a12 a13 a23 obtain ⟨y, y2, y3, y4⟩ := sk33_line_common_vertex H htri e2 e3 e4 h2 h3 h4 a23 a24 a34 have hxy : x = y := by by_contra h exact n23 (((Sym2.mem_and_mem_iff h).1 ⟨x2, y2⟩).trans ((Sym2.mem_and_mem_iff h).1 ⟨x3, y3⟩).symm) subst hxy obtain ⟨a, rfl⟩ := Sym2.mem_iff_exists.1 x1 obtain ⟨b, rfl⟩ := Sym2.mem_iff_exists.1 x2 obtain ⟨c, rfl⟩ := Sym2.mem_iff_exists.1 x3 obtain ⟨d, rfl⟩ := Sym2.mem_iff_exists.1 y4 rw [SimpleGraph.mem_edgeSet] at h1 h2 h3 h4 rcases hdeg x a b c d h1 h2 h3 h4 with rfl | rfl | rfl | rfl | rfl | rfl <;> simp_alltheorem sk33_line_no_claw {V : Type*} (e0 f1 f2 f3 : Sym2 V) (a1 : ∃ v, v ∈ e0 ∧ v ∈ f1) (a2 : ∃ v, v ∈ e0 ∧ v ∈ f2) (a3 : ∃ v, v ∈ e0 ∧ v ∈ f3) (b12 : ¬ ∃ v, v ∈ f1 ∧ v ∈ f2) (b13 : ¬ ∃ v, v ∈ f1 ∧ v ∈ f3) (b23 : ¬ ∃ v, v ∈ f2 ∧ v ∈ f3) : False := by induction e0 using Sym2.ind with | h a b => obtain ⟨v1, hv1, w1⟩ := a1 obtain ⟨v2, hv2, w2⟩ := a2 obtain ⟨v3, hv3, w3⟩ := a3 rw [Sym2.mem_iff] at hv1 hv2 hv3 rcases hv1 with e1 | e1 <;> rcases hv2 with e2 | e2 <;> rcases hv3 with e3 | e3 <;> subst e1 e2 e3 <;> first | exact b12 ⟨_, w1, w2⟩ | exact b13 ⟨_, w1, w3⟩ | exact b23 ⟨_, w2, w3⟩def sk33_adjB (x y : Fin 7) : Bool := [(0, 6), (6, 3), (0, 4), (0, 5), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5)].any (fun p : ℕ × ℕ => (p.1 == x.val && p.2 == y.val) || (p.2 == x.val && p.1 == y.val))theorem sk33_adj_iff (x y : Fin 7) : h_subdivided_k33.Adj x y ↔ sk33_adjB x y = true := by fin_cases x <;> fin_cases y <;> simp [h_subdivided_k33, sk33_adjB]theorem sk33_tri : ∀ x y z, h_subdivided_k33.Adj x y → h_subdivided_k33.Adj y z → h_subdivided_k33.Adj x z → False := by simp only [sk33_adj_iff]; decidetheorem sk33_deg : ∀ x a b c d, h_subdivided_k33.Adj x a → h_subdivided_k33.Adj x b → h_subdivided_k33.Adj x c → h_subdivided_k33.Adj x d → a = b ∨ a = c ∨ a = d ∨ b = c ∨ b = d ∨ c = d := by simp only [sk33_adj_iff]; decidetheorem subdivided_k33_line_graph_no_k4_claw_diamond : (¬ SimpleGraph.IsIndContained (⊤ : SimpleGraph (Fin 4)) h_subdivided_k33.lineGraph) ∧ IsClawFree h_subdivided_k33.lineGraph ∧ is_diamond_free h_subdivided_k33.lineGraph := by have adj : ∀ {W : Type} (K : SimpleGraph W) (f : K ↪g h_subdivided_k33.lineGraph) (i j : W), K.Adj i j → (f i : Sym2 (Fin 7)) ≠ f j ∧ ∃ v, v ∈ (f i : Sym2 (Fin 7)) ∧ v ∈ (f j : Sym2 (Fin 7)) := by intro W K f i j h have := f.map_rel_iff.2 h rw [SimpleGraph.lineGraph_adj_iff_exists] at this exact ⟨fun e => this.1 (Subtype.ext e), this.2⟩ refine ⟨?_, ?_, ?_⟩ · rintro ⟨f⟩ have A : ∀ i j : Fin 4, i ≠ j → (f i : Sym2 (Fin 7)) ≠ f j ∧ ∃ v, v ∈ (f i : Sym2 (Fin 7)) ∧ v ∈ (f j : Sym2 (Fin 7)) := fun i j h => adj _ f i j h exact sk33_line_no_four _ sk33_tri sk33_deg _ _ _ _ (f 0).2 (f 1).2 (f 2).2 (f 3).2 (A 0 1 (by decide)).1 (A 0 2 (by decide)).1 (A 0 3 (by decide)).1 (A 1 2 (by decide)).1 (A 1 3 (by decide)).1 (A 2 3 (by decide)).1 (A 0 1 (by decide)).2 (A 0 2 (by decide)).2 (A 1 2 (by decide)).2 (A 1 3 (by decide)).2 (A 2 3 (by decide)).2 · rintro ⟨f⟩ have A : ∀ j : Fin 3, ∃ v, v ∈ (f (Sum.inl 0) : Sym2 (Fin 7)) ∧ v ∈ (f (Sum.inr j) : Sym2 (Fin 7)) := fun j => (adj _ f (Sum.inl 0) (Sum.inr j) (by simp)).2 have B : ∀ i j : Fin 3, i ≠ j → ¬ ∃ v, v ∈ (f (Sum.inr i) : Sym2 (Fin 7)) ∧ v ∈ (f (Sum.inr j) : Sym2 (Fin 7)) := by intro i j hij hv have hne : f (Sum.inr i) ≠ f (Sum.inr j) := fun e => hij (by simpa using f.injective e) have : h_subdivided_k33.lineGraph.Adj (f (Sum.inr i)) (f (Sum.inr j)) := by rw [SimpleGraph.lineGraph_adj_iff_exists] exact ⟨hne, hv⟩ rw [f.map_rel_iff] at this simp at this exact sk33_line_no_claw _ _ _ _ (A 0) (A 1) (A 2) (B 0 1 (by decide)) (B 0 2 (by decide)) (B 1 2 (by decide)) · rintro ⟨f⟩ have A : ∀ i j : Fin 4, diamond_graph.Adj i j → (f i : Sym2 (Fin 7)) ≠ f j ∧ ∃ v, v ∈ (f i : Sym2 (Fin 7)) ∧ v ∈ (f j : Sym2 (Fin 7)) := fun i j h => adj _ f i j h have n03 : (f 0 : Sym2 (Fin 7)) ≠ f 3 := fun e => absurd (f.injective (Subtype.ext e)) (by decide) exact sk33_line_no_four _ sk33_tri sk33_deg _ _ _ _ (f 0).2 (f 1).2 (f 2).2 (f 3).2 (A 0 1 (by simp [diamond_graph])).1 (A 0 2 (by simp [diamond_graph])).1 n03 (A 1 2 (by simp [diamond_graph])).1 (A 1 3 (by simp [diamond_graph])).1 (A 2 3 (by simp [diamond_graph])).1 (A 0 1 (by simp [diamond_graph])).2 (A 0 2 (by simp [diamond_graph])).2 (A 1 2 (by simp [diamond_graph])).2 (A 1 3 (by simp [diamond_graph])).2 (A 2 3 (by simp [diamond_graph])).2