truncation_local_states_strong_coloring_iff
Lemma 2.1 of arXiv:2610.41950. Let G be a loopless cubic multigraph, given by ends : E → Sym2 V (no Fintype or Finite instance on V or E is assumed: the cubic condition already makes the set of edges at each vertex finite, and the lemma is local) with no edge a loop (¬ (ends e).IsDiag) and every vertex on exactly three edges (Set.ncard {e | v ∈ ends e} = 3), and let Ω be a set of six colours (Fintype.card Ω = 6). Let c h : V → E → Ω be a local state at every vertex v: the six colours c v e and h v e (e ranging over the three edges at v) are pairwise distinct, i.e. ∀ v e f, v ∈ ends e → v ∈ ends f → c v e = c v f → e = f, the same for h, and h v e ≠ c v f for all edges e, f at v (so h v is a bijection from the edges at v onto I_v = Ω \ c v(edges at v)). Then the local states define a strong edge-colouring of the truncation T(G) (truncation_local_states_define_strong_coloring ends c h) if and only if for every edge e and all u v with ends e = s(u, v): c u e = c v e and the exposed pairs P_u(e) = truncation_exposed_pair ends c h u e and P_v(e) = truncation_exposed_pair ends c h v e are disjoint (Disjoint of the two sets).
Statement
theorem truncation_local_states_strong_coloring_iff {V E Ω : Type*} [Fintype Ω] (hΩ : Fintype.card Ω = 6) (ends : E → Sym2 V) (hloop : ∀ e, ¬ (ends e).IsDiag) (hcubic : ∀ v, Set.ncard {e | v ∈ ends e} = 3) (c h : V → E → Ω) (hc : ∀ v e f, v ∈ ends e → v ∈ ends f → c v e = c v f → e = f) (hh : ∀ v e f, v ∈ ends e → v ∈ ends f → h v e = h v f → e = f) (hch : ∀ v e f, v ∈ ends e → v ∈ ends f → h v e ≠ c v f) : truncation_local_states_define_strong_coloring ends c h ↔ ∀ e u v, ends e = s(u, v) → c u e = c v e ∧ Disjoint (truncation_exposed_pair ends c h u e) (truncation_exposed_pair ends c h v e)
- Formalizes
- arXiv:2610.41950 (Strong edge-colourings of truncations of cubic graphs), Lemma 2.1 (the first, signature form; the equivalent form (2.3) and the pole version are not stated)
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- multigraph_truncationThe truncation T(G) of a multigraph G with vertex type V and edge type E, the multigraph given by its endpoint map ends : E → Sym2 V…
- simple_graph_is_strong_edge_coloringFor a simple graph G on W and a colour map χ : Sym2 W → Ω (a colour for each unordered pair; only its values on edges of G matter), χ is a…
- truncation_exposed_pairFor a multigraph given by ends : E → Sym2 V and colour assignments c h : V → E → Ω (c v e is the external colour at the port (v, e), h v e…
- truncation_local_states_define_strong_coloringThe local states (c, h), with c h : V → E → Ω, define a strong edge-colouring of the truncation multigraph_truncation ends: there is χ :…
- multigraph_cubic_third_edgeIn a multigraph (ends : E → Sym2 V) where every vertex lies on exactly three edges, two distinct edges e ≠ f at v leave a third edge g at…
- truncation_local_state_internal_coverWith six colours, a local state at v (c v injective on the three edges at v, h v injective there, and no h v e equal to any c v f) has h v…
Read back from the Lean
For any types $V$, $E$, and $\Omega$, where $\Omega$ is a finite type of cardinality 6, given an incidence function $\mathrm{ends} : E \to \mathrm{Sym2}(V)$ representing a loopless multigraph ($\forall e, \neg (\mathrm{ends}(e)).\mathrm{IsDiag}$) that is cubic ($\forall v \in V$, the number of incident edges $\{e \mid v \in \mathrm{ends}(e)\}$ has cardinality 3), and given color assignments $c, h : V \to E \to \Omega$ such that for every vertex $v$:
1. $c(v, \cdot)$ is injective on edges incident to $v$,
2. $h(v, \cdot)$ is injective on edges incident to $v$, and
3. the values $\{c(v, e) \mid v \in \mathrm{ends}(e)\}$ and $\{h(v, f) \mid v \in \mathrm{ends}(f)\}$ are mutually disjoint,
the local state coloring conditions defined by $c$ and $h$ admit a strong edge coloring on the multigraph truncation (truncation_local_states_define_strong_coloring ends c h) if and only if:
for every edge $e \in E$ and vertices $u, v \in V$ such that $\mathrm{ends}(e) = s(u, v)$,
both of the following hold:
- $c(u, e) = c(v, e)$, and
- the exposed color pairs $\mathrm{truncation\_exposed\_pair}(\mathrm{ends}, c, h, u, e)$ and $\mathrm{truncation\_exposed\_pair}(\mathrm{ends}, c, h, v, e)$ are disjoint.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The equivalence is proved in two directions. In the forward direction, assuming a strong edge-colouring χ defining the local states, the external edge for an edge e = uv forces c(u, e) = c(v, e); if an exposed colour belonged to both P_u(e) and P_v(e), it would colour two internal edges at u and v connected by the external edge e, placing two monochromatic edges at distance 2 in T(G) and violating the strong colouring property. In the backward direction, an edge-colouring χ is defined via Hilbert choice according to the local states. The strong colouring condition is then verified by showing that conflicting edges either meet at the same multigraph vertex (where distinctness follows from the injectivity and disjointness of c and h) or are linked by an external edge e (where internal edges receive colours in the exposed pairs P_u(e) and P_v(e), which are disjoint by hypothesis).
Ports of the truncation graph and unordered pairs representing edges satisfy basic extensionality.
Two ports p, q (elements of the subtype of pairs (v, e) with v ∈ ends(e)) are equal whenever their vertex and edge projections agree (port_ext). Moreover, if two distinct vertices u and w are both incident to an edge e, then the unordered pair ends(e) is uniquely identified as s(u, w) (ends_eq).
uses
Subtype.ext,Prod.ext,Sym2.mem_and_mem_iffclassical have port_ext : ∀ p q : {p : V × E // p.1 ∈ ends p.2}, p.1.1 = q.1.1 → p.1.2 = q.1.2 → p = q := fun p q h1 h2 => Subtype.ext (Prod.ext h1 h2) have ends_eq : ∀ e u w, u ∈ ends e → w ∈ ends e → u ≠ w → ends e = s(u, w) := fun e u w hu hw hne => (Sym2.mem_and_mem_iff hne).1 ⟨hu, hw⟩
Under the forward assumption, any edge e with ends s(u, v) has distinct endpoints u ≠ v, defining two distinct ports p = (u, e) and q = (v, e).
We assume χ is a strong edge-colouring defining the local states. For any edge e with ends(e) = s(u, v), both u and v belong to ends(e). Because G is loopless, u ≠ v. Consequently, the ports p = (u, e) and q = (v, e) are distinct because their vertex components differ.
uses
Sym2.mem_mk_left,Sym2.mem_mk_right,Sym2.mk_isDiag_iff.2,congrArgconstructor · rintro ⟨χ, hs, hext, hint⟩ e u v huv have hu : u ∈ ends e := by rw [huv]; exact Sym2.mem_mk_left u v have hv : v ∈ ends e := by rw [huv]; exact Sym2.mem_mk_right u v have hne : u ≠ v := by intro h' apply hloop e rw [huv, h'] exact Sym2.mk_isDiag_iff.2 rfl let p : {p : V × E // p.1 ∈ ends p.2} := ⟨(u, e), hu⟩ let q : {p : V × E // p.1 ∈ ends p.2} := ⟨(v, e), hv⟩ have hpq : p ≠ q := fun h' => hne (congrArg (fun x : {p : V × E // p.1 ∈ ends p.2} => x.1.1) h')
The external state colour c agrees across the endpoints of e: c(u, e) = c(v, e).
The ports p and q form an external edge s(p, q) in the truncation graph T(G). By the external edge colouring hypothesis (hext), χ(s(p, q)) = c(u, e) and χ(s(q, p)) = c(v, e). Since s(p, q) = s(q, p), we obtain c(u, e) = c(v, e).
uses
Sym2.eq_swaprefine ⟨?_, ?_⟩ · have h1 : χ s(p, q) = c u e := hext p q hpq rfl have h2 : χ s(q, p) = c v e := hext q p hpq.symm rfl rw [Sym2.eq_swap] at h2 exact h1.symm.trans h2
If a colour ω lies in both exposed pairs P_u(e) and P_v(e), it is the h-state of edges g ≠ e at u and g' ≠ e at v, each leaving a third edge.
To show disjointness of the exposed pairs P_u(e) and P_v(e), suppose for contradiction that some colour ω lies in both. By truncation_local_state_internal_cover, since ω is not in the image of c at u or v, it must satisfy ω = h(u, g) for an edge g at u and ω = h(v, g') for an edge g' at v. Since ω avoids h(u, e) and h(v, e), we have g ≠ e and g' ≠ e. Because G is cubic, there exist unique third edges k at u (distinct from e, g) and k' at v (distinct from e, g').
uses
Set.disjoint_left,truncation_local_state_internal_cover,multigraph_cubic_third_edge· rw [Set.disjoint_left] rintro ω ⟨hωu, hωu'⟩ ⟨hωv, hωv'⟩ obtain ⟨g, hg, hgω⟩ := truncation_local_state_internal_cover hΩ hcubic hc hh hch hωu obtain ⟨g', hg', hgω'⟩ := truncation_local_state_internal_cover hΩ hcubic hc hh hch hωv have hge : g ≠ e := by rintro rfl; exact hωu' hgω.symm have hge' : g' ≠ e := by rintro rfl; exact hωv' hgω'.symm obtain ⟨k, hk, hke, hkg, -⟩ := multigraph_cubic_third_edge hcubic hu hg hge.symm obtain ⟨k', hk', hke', hkg', -⟩ := multigraph_cubic_third_edge hcubic hv hg' hge'.symm
The ports corresponding to the three incident edges at u and v are pairwise distinct.
We define the remaining ports a_2 = (u, k) and r = (u, g) at vertex u, and b_2 = (v, k') and r' = (v, g') at vertex v. Because the edges e, k, g at u and e, k', g' at v are pairwise distinct, the ports p, a_2, r at u are pairwise distinct, as are q, b_2, r' at v.
uses
congrArglet a2 : {p : V × E // p.1 ∈ ends p.2} := ⟨(u, k), hk⟩ let r : {p : V × E // p.1 ∈ ends p.2} := ⟨(u, g), hg⟩ let b2 : {p : V × E // p.1 ∈ ends p.2} := ⟨(v, k'), hk'⟩ let r' : {p : V × E // p.1 ∈ ends p.2} := ⟨(v, g'), hg'⟩ have hpa2 : p ≠ a2 := fun h' => hke (congrArg (fun x : {p : V × E // p.1 ∈ ends p.2} => x.1.2) h').symm have hpr : p ≠ r := fun h' => hge (congrArg (fun x : {p : V × E // p.1 ∈ ends p.2} => x.1.2) h').symm have ha2r : a2 ≠ r := fun h' => hkg (congrArg (fun x : {p : V × E // p.1 ∈ ends p.2} => x.1.2) h') have hqb2 : q ≠ b2 := fun h' => hke' (congrArg (fun x : {p : V × E // p.1 ∈ ends p.2} => x.1.2) h').symm have hqr' : q ≠ r' := fun h' => hge' (congrArg (fun x : {p : V × E // p.1 ∈ ends p.2} => x.1.2) h').symm have hb2r' : b2 ≠ r' := fun h' => hkg' (congrArg (fun x : {p : V × E // p.1 ∈ ends p.2} => x.1.2) h')
The exposed pairs P_u(e) and P_v(e) are disjoint.
The internal edges s(p, a_2) at u (opposite r = (u, g)) and s(q, b_2) at v (opposite r' = (v, g')) receive colours h(u, g) = ω and h(v, g') = ω by the internal edge condition (hint). However, their endpoints p and q are adjacent in T(G) via the external edge s(p, q), so the two edges are at distance at most 2. They are distinct edges because u ≠ v. The strong edge-colouring property of χ forbids them from sharing the colour ω, producing a contradiction.
uses
SimpleGraph.mem_edgeSet,Or.inl,Or.inr,Sym2.mem_mk_left,Sym2.mem_iff.1,congrArghave hx : χ s(p, a2) = ω := by rw [← hgω]; exact hint p a2 r hpa2 hpr ha2r rfl rfl have hy : χ s(q, b2) = ω := by rw [← hgω']; exact hint q b2 r' hqb2 hqr' hb2r' rfl rfl refine hs s(p, a2) ((SimpleGraph.mem_edgeSet _).2 ⟨hpa2, Or.inl rfl⟩) s(q, b2) ((SimpleGraph.mem_edgeSet _).2 ⟨hqb2, Or.inl rfl⟩) ?_ (Or.inr ⟨p, q, Sym2.mem_mk_left _ _, Sym2.mem_mk_left _ _, ⟨hpq, Or.inr rfl⟩⟩) (hx.trans hy.symm) intro h' have hmem : p ∈ s(q, b2) := h' ▸ Sym2.mem_mk_left p a2 rcases Sym2.mem_iff.1 hmem with h'' | h'' · exact hne (congrArg (fun x : {p : V × E // p.1 ∈ ends p.2} => x.1.1) h'') · exact hne (congrArg (fun x : {p : V × E // p.1 ∈ ends p.2} => x.1.1) h'')
Under the backward hypothesis, a candidate colouring χ on T(G) is defined via Hilbert choice.
Assuming the local compatibility conditions, we define a relation Rel specifying that external edges receive colour c(p.1.1, p.1.2) and internal edges opposite port r receive colour h(r.1.1, r.1.2). Since |Ω| = 6 > 0, Ω is non-empty, and we define χ by Hilbert choice (Classical.epsilon).
uses
Fintype.card_pos_iff.mp,Classical.epsilon· intro H have : Nonempty Ω := Fintype.card_pos_iff.mp (by omega) let Rel : Sym2 {p : V × E // p.1 ∈ ends p.2} → Ω → Prop := fun z ω => (∃ p q : {p : V × E // p.1 ∈ ends p.2}, z = s(p, q) ∧ p ≠ q ∧ p.1.2 = q.1.2 ∧ ω = c p.1.1 p.1.2) ∨ (∃ p q r : {p : V × E // p.1 ∈ ends p.2}, z = s(p, q) ∧ p ≠ q ∧ p ≠ r ∧ q ≠ r ∧ p.1.1 = q.1.1 ∧ p.1.1 = r.1.1 ∧ ω = h r.1.1 r.1.2) let χ : Sym2 {p : V × E // p.1 ∈ ends p.2} → Ω := fun z => Classical.epsilon (Rel z)
At any vertex with two distinct ports p, q, the third port r is uniquely determined.
We prove port_third: since each vertex has degree 3, any two ports r and r' at the same vertex that are both distinct from p and q must correspond to the unique third incident edge, and hence r = r'.
uses
multigraph_cubic_third_edgehave port_third : ∀ p q r r' : {p : V × E // p.1 ∈ ends p.2}, p ≠ q → p.1.1 = q.1.1 → r ≠ p → r ≠ q → r' ≠ p → r' ≠ q → r.1.1 = p.1.1 → r'.1.1 = p.1.1 → r = r' := by intro p q r r' hpq hv hrp hrq hr'p hr'q hr hr' have hpe : p.1.1 ∈ ends p.1.2 := p.2 have hqe : p.1.1 ∈ ends q.1.2 := by rw [hv]; exact q.2 have hef : p.1.2 ≠ q.1.2 := fun h' => hpq (port_ext p q hv h') obtain ⟨g, -, -, -, hall⟩ := multigraph_cubic_third_edge hcubic hpe hqe hef have hrg : r.1.2 = g := by have hre : p.1.1 ∈ ends r.1.2 := by rw [← hr]; exact r.2 rcases hall _ hre with h' | h' | h' · exact absurd (port_ext r p hr h') hrp · exact absurd (port_ext r q (hr.trans hv) h') hrq · exact h' have hr'g : r'.1.2 = g := by have hre : p.1.1 ∈ ends r'.1.2 := by rw [← hr']; exact r'.2 rcases hall _ hre with h' | h' | h' · exact absurd (port_ext r' p hr' h') hr'p · exact absurd (port_ext r' q (hr'.trans hv) h') hr'q · exact h' exact port_ext r r' (hr.trans hr'.symm) (hrg.trans hr'g.symm)
The candidate colouring χ assigns every external edge its required colour c(p.1.1, p.1.2).
For an external edge s(p, q), the specification of Classical.epsilon guarantees that Rel holds. The internal edge alternative is impossible because the endpoints of an external edge lie at different multigraph vertices. In the external alternative, whether the edge is oriented as s(p, q) or s(q, p), the colour is c(p.1.1, p.1.2) by the assumption c(u, e) = c(v, e).
uses
Or.inl,Classical.epsilon_spec,Sym2.eq_iff.1have hext' : ∀ p q : {p : V × E // p.1 ∈ ends p.2}, p ≠ q → p.1.2 = q.1.2 → χ s(p, q) = c p.1.1 p.1.2 := by intro p q hpq he have hR : Rel s(p, q) (c p.1.1 p.1.2) := Or.inl ⟨p, q, rfl, hpq, he, rfl⟩ have hspec : Rel s(p, q) (χ s(p, q)) := Classical.epsilon_spec ⟨_, hR⟩ have hvne : p.1.1 ≠ q.1.1 := fun h' => hpq (port_ext p q h' he) rcases hspec with ⟨p', q', hz, hpq', he', hω⟩ | ⟨p', q', r', hz, hpq', hpr', hqr', hv1, hv2, hω⟩ · rw [hω] rcases Sym2.eq_iff.1 hz with ⟨h1, h2⟩ | ⟨h1, h2⟩ · rw [← h1] · rw [← h2, ← he] have hq : q.1.1 ∈ ends p.1.2 := by rw [he]; exact q.2 exact ((H p.1.2 p.1.1 q.1.1 (ends_eq _ _ _ p.2 hq hvne)).1).symm · exfalso have : p.1.1 = q.1.1 := by rcases Sym2.eq_iff.1 hz with ⟨h1, h2⟩ | ⟨h1, h2⟩ · rw [h1, h2]; exact hv1 · rw [h1, h2]; exact hv1.symm exact hvne this
The candidate colouring χ assigns every internal edge its required colour h(r.1.1, r.1.2).
For an internal edge s(p, q) at vertex v opposite port r, the external alternative in Rel is ruled out because both ports are at vertex v, which would force them to be identical. In the internal alternative, any third port r' at v must equal r by port_third, ensuring χ(s(p, q)) = h(r.1.1, r.1.2).
uses
Or.inr,Classical.epsilon_spec,Sym2.eq_iff.1have hint' : ∀ p q r : {p : V × E // p.1 ∈ ends p.2}, p ≠ q → p ≠ r → q ≠ r → p.1.1 = q.1.1 → p.1.1 = r.1.1 → χ s(p, q) = h r.1.1 r.1.2 := by intro p q r hpq hpr hqr hv hvr have hR : Rel s(p, q) (h r.1.1 r.1.2) := Or.inr ⟨p, q, r, rfl, hpq, hpr, hqr, hv, hvr, rfl⟩ have hspec : Rel s(p, q) (χ s(p, q)) := Classical.epsilon_spec ⟨_, hR⟩ rcases hspec with ⟨p', q', hz, hpq', he', hω⟩ | ⟨p', q', r', hz, hpq', hpr', hqr', hv1, hv2, hω⟩ · exfalso have : p.1.2 = q.1.2 := by rcases Sym2.eq_iff.1 hz with ⟨h1, h2⟩ | ⟨h1, h2⟩ · rw [h1, h2]; exact he' · rw [h1, h2]; exact he'.symm exact hpq (port_ext p q hv this) · rw [hω] have key : r' ≠ p ∧ r' ≠ q ∧ r'.1.1 = p.1.1 := by rcases Sym2.eq_iff.1 hz with ⟨h1, h2⟩ | ⟨h1, h2⟩ · rw [h1, h2]; exact ⟨hpr'.symm, hqr'.symm, hv2.symm⟩ · rw [h1, h2]; exact ⟨hqr'.symm, hpr'.symm, hv2.symm.trans hv1⟩ have := port_third p q r' r hpq hv key.1 key.2.1 hpr.symm hqr.symm key.2.2 hvr.symm rw [this]
Internal edges opposite the same port are identical, and the external edge at a port is unique.
We prove int_eq (two internal edges at the same vertex opposite the same port r represent the same edge in T(G)) and ext_eq (an edge e has only two endpoints, so a port a = (u, e) has a unique counterpart b = (v, e) sharing edge e).
uses
Sym2.eq_swap,Sym2.mem_iffrefine ⟨χ, ?_, hext', hint'⟩ -- two internal edges at the same vertex with the same opposite port are equal have int_eq : ∀ a b a' b' r : {p : V × E // p.1 ∈ ends p.2}, a ≠ b → a' ≠ b' → a.1.1 = b.1.1 → a'.1.1 = b'.1.1 → a'.1.1 = a.1.1 → r ≠ a → r ≠ b → r ≠ a' → r ≠ b' → r.1.1 = a.1.1 → s(a, b) = s(a', b') := by intro a b a' b' r hab ha'b' hv hv' hw hra hrb hra' hrb' hr have ha' : a' = a ∨ a' = b := by by_contra hcon push Not at hcon exact hra' (port_third a b r a' hab hv hra hrb hcon.1 hcon.2 hr hw) have hb' : b' = a ∨ b' = b := by by_contra hcon push Not at hcon exact hrb' (port_third a b r b' hab hv hra hrb hcon.1 hcon.2 hr (hv'.symm.trans hw)) rcases ha' with rfl | rfl <;> rcases hb' with rfl | rfl <;> first | rfl | exact Sym2.eq_swap | exact absurd rfl ha'b' have ext_eq : ∀ a b b' : {p : V × E // p.1 ∈ ends p.2}, a ≠ b → a ≠ b' → a.1.2 = b.1.2 → a.1.2 = b'.1.2 → b = b' := by intro a b b' hab hab' hx hx' have hvne : a.1.1 ≠ b.1.1 := fun h' => hab (port_ext a b h' hx) have hvne' : a.1.1 ≠ b'.1.1 := fun h' => hab' (port_ext a b' h' hx') have hb : b'.1.1 ∈ ends a.1.2 := by rw [hx']; exact b'.2 have hb0 : b.1.1 ∈ ends a.1.2 := by rw [hx]; exact b.2 rw [ends_eq a.1.2 a.1.1 b.1.1 a.2 hb0 hvne, Sym2.mem_iff] at hb rcases hb with h' | h' · exact absurd h'.symm hvne' · exact port_ext b b' h'.symm (hx.symm.trans hx') -- the colour of an internal edge at `a`
Every internal edge s(a, b) at vertex a.1.1 has colour h(a.1.1, g) for the unique third incident edge g.
By the cubic multigraph condition, there is a unique third edge g at vertex a.1.1 distinct from a.1.2 and b.1.2. Setting r = (a.1.1, g), lemma hint' yields χ(s(a, b)) = h(a.1.1, g).
uses
multigraph_cubic_third_edge,congrArghave int_col : ∀ a b : {p : V × E // p.1 ∈ ends p.2}, a ≠ b → a.1.1 = b.1.1 → ∃ g, a.1.1 ∈ ends g ∧ g ≠ a.1.2 ∧ g ≠ b.1.2 ∧ χ s(a, b) = h a.1.1 g := by intro a b hab hv have hb : a.1.1 ∈ ends b.1.2 := by rw [hv]; exact b.2 have hef : a.1.2 ≠ b.1.2 := fun h' => hab (port_ext a b hv h') obtain ⟨g, hg, hga, hgb, -⟩ := multigraph_cubic_third_edge hcubic a.2 hb hef refine ⟨g, hg, hga, hgb, ?_⟩ have hra : a ≠ ⟨(a.1.1, g), hg⟩ := fun h' => hga (congrArg (fun x : {p : V × E // p.1 ∈ ends p.2} => x.1.2) h').symm have hrb : b ≠ ⟨(a.1.1, g), hg⟩ := fun h' => hgb (congrArg (fun x : {p : V × E // p.1 ∈ ends p.2} => x.1.2) h').symm exact hint' a b ⟨(a.1.1, g), hg⟩ hab hra hrb hv rfl
Two distinct edges of T(G) meeting at the same multigraph vertex receive distinct colours under χ.
We establish around and around2: if two distinct edges of T(G) have ports at the same vertex v, their colours differ. If both are internal, their colours differ by injectivity of h; if one is internal and one external, their colours differ because h and c have disjoint ranges; if both are external, their colours differ by injectivity of c.
uses
congrArg,Sym2.mem_iff_exists.1,SimpleGraph.mem_edgeSethave around : ∀ a b a' b' : {p : V × E // p.1 ∈ ends p.2}, (multigraph_truncation ends).Adj a b → (multigraph_truncation ends).Adj a' b' → a.1.1 = a'.1.1 → s(a, b) ≠ s(a', b') → χ s(a, b) ≠ χ s(a', b') := by intro a b a' b' hab ha'b' hw hne heq obtain ⟨hab1, hab2⟩ := hab obtain ⟨ha'b'1, ha'b'2⟩ := ha'b' rcases hab2 with hi | hx <;> rcases ha'b'2 with hi' | hx' · obtain ⟨g, hg, hga, hgb, hcol⟩ := int_col a b hab1 hi obtain ⟨g', hg', hga', hgb', hcol'⟩ := int_col a' b' ha'b'1 hi' rw [hcol, hcol', ← hw] at heq have hg'' : a.1.1 ∈ ends g' := by rw [hw]; exact hg' have hgg : g = g' := hh _ _ _ hg hg'' heq subst hgg refine hne (int_eq a b a' b' ⟨(a.1.1, g), hg⟩ hab1 ha'b'1 hi hi' hw.symm ?_ ?_ ?_ ?_ rfl) · exact fun h' => hga (congrArg (fun x : {p : V × E // p.1 ∈ ends p.2} => x.1.2) h') · exact fun h' => hgb (congrArg (fun x : {p : V × E // p.1 ∈ ends p.2} => x.1.2) h') · exact fun h' => hga' (congrArg (fun x : {p : V × E // p.1 ∈ ends p.2} => x.1.2) h') · exact fun h' => hgb' (congrArg (fun x : {p : V × E // p.1 ∈ ends p.2} => x.1.2) h') · obtain ⟨g, hg, -, -, hcol⟩ := int_col a b hab1 hi rw [hcol, hext' a' b' ha'b'1 hx', ← hw] at heq have ha'e : a.1.1 ∈ ends a'.1.2 := by rw [hw]; exact a'.2 exact hch _ _ _ hg ha'e heq · obtain ⟨g', hg', -, -, hcol'⟩ := int_col a' b' ha'b'1 hi' rw [hext' a b hab1 hx, hcol', ← hw] at heq have hg'' : a.1.1 ∈ ends g' := by rw [hw]; exact hg' exact hch _ _ _ hg'' a.2 heq.symm · rw [hext' a b hab1 hx, hext' a' b' ha'b'1 hx', ← hw] at heq have ha'e : a.1.1 ∈ ends a'.1.2 := by rw [hw]; exact a'.2 have hee : a.1.2 = a'.1.2 := hc _ _ _ a.2 ha'e heq have haa : a = a' := port_ext a a' hw hee subst haa exact hne (by rw [ext_eq a b b' hab1 ha'b'1 hx hx']) have around2 : ∀ x y : Sym2 {p : V × E // p.1 ∈ ends p.2}, x ∈ (multigraph_truncation ends).edgeSet → y ∈ (multigraph_truncation ends).edgeSet → x ≠ y → ∀ z z', z ∈ x → z' ∈ y → z.1.1 = z'.1.1 → χ x ≠ χ y := by intro x y hx hy hxy z z' hz hz' hzz obtain ⟨b, rfl⟩ := Sym2.mem_iff_exists.1 hz obtain ⟨b', rfl⟩ := Sym2.mem_iff_exists.1 hz' exact around z b z' b' ((SimpleGraph.mem_edgeSet _).1 hx) ((SimpleGraph.mem_edgeSet _).1 hy) hzz hxy
The candidate colouring χ is a strong edge-colouring of T(G), establishing the equivalence.
We verify that distinct conflicting edges x, y in T(G) receive different colours. If x and y share a port or are joined by an internal edge, their ports meet at the same multigraph vertex, so around2 applies. If they are joined by an external edge e between vertices u and w: when both x and y are internal, their colours lie in the exposed pairs P_u(e) and P_w(e), which are disjoint by assumption; when either x or y is external, uniqueness of the external edge (ext_eq) forces it to share a port with the other edge, again reducing to around2.
uses
SimpleGraph.mem_edgeSet,Sym2.mem_iff_exists.1,Set.disjoint_left.1,Sym2.mem_mk_left,Sym2.mem_mk_rightintro x hx y hy hxy hconf rcases hconf with ⟨z, hz1, hz2⟩ | ⟨u, w, hu, hw, huw⟩ · exact around2 x y hx hy hxy z z hz1 hz2 rfl · obtain ⟨huw1, huw2⟩ := huw rcases huw2 with hv | he · exact around2 x y hx hy hxy u w hu hw hv · obtain ⟨u2, rfl⟩ := Sym2.mem_iff_exists.1 hu obtain ⟨w2, rfl⟩ := Sym2.mem_iff_exists.1 hw have hadj := (SimpleGraph.mem_edgeSet _).1 hx have hadj' := (SimpleGraph.mem_edgeSet _).1 hy have hvne : u.1.1 ≠ w.1.1 := fun h' => huw1 (port_ext u w h' he) by_cases hx2 : u.1.1 = u2.1.1 · by_cases hy2 : w.1.1 = w2.1.1 · obtain ⟨g, hg, hgu, -, hcol⟩ := int_col u u2 hadj.1 hx2 obtain ⟨g', hg', hgw, -, hcol'⟩ := int_col w w2 hadj'.1 hy2 have hwe : w.1.1 ∈ ends u.1.2 := by rw [he]; exact w.2 have hdisj := (H u.1.2 u.1.1 w.1.1 (ends_eq _ _ _ u.2 hwe hvne)).2 have m1 : χ s(u, u2) ∈ truncation_exposed_pair ends c h u.1.1 u.1.2 := by rw [hcol] exact ⟨fun f hf => (hch _ _ _ hg hf).symm, fun h' => hgu (hh _ _ _ hg u.2 h')⟩ have m2 : χ s(w, w2) ∈ truncation_exposed_pair ends c h w.1.1 u.1.2 := by rw [hcol', he] exact ⟨fun f hf => (hch _ _ _ hg' hf).symm, fun h' => hgw (hh _ _ _ hg' w.2 h')⟩ intro heq rw [heq] at m1 exact Set.disjoint_left.1 hdisj m1 m2 · -- `s(w, w2)` is external, so `w2 = u` have hw2 : w.1.2 = w2.1.2 := hadj'.2.resolve_left hy2 have hwu : w ≠ u := fun h' => huw1 h'.symm have : w2 = u := ext_eq w w2 u hadj'.1 hwu hw2 he.symm subst this exact around2 _ _ hx hy hxy w2 w2 (Sym2.mem_mk_left _ _) (Sym2.mem_mk_right _ _) rfl · have hu2 : u.1.2 = u2.1.2 := hadj.2.resolve_left hx2 have : u2 = w := ext_eq u u2 w hadj.1 huw1 hu2 he subst this exact around2 _ _ hx hy hxy u2 u2 (Sym2.mem_mk_right _ _) (Sym2.mem_mk_left _ _) rfl
Classical.epsilon- An element is chosen noncomputably from a non-empty type satisfying a predicate if one exists
Classical.epsilon_spec- If there exists an element satisfying a predicate, Classical.epsilon returns a witness satisfying it
Fintype.card_pos_iff.mp- A finite type with strictly positive cardinality is non-empty
Or.inl- If a proposition holds, then any disjunction with that proposition on the left holds
Or.inr- If a proposition holds, then any disjunction with that proposition on the right holds
Prod.ext- Two ordered pairs are equal if their respective components are equal
Set.disjoint_left- Two sets are disjoint if and only if no element of the first set belongs to the second
Set.disjoint_left.1- If two sets are disjoint, an element of the first cannot belong to the second
SimpleGraph.mem_edgeSet- An unordered pair is an edge of a simple graph if and only if its endpoints are adjacent
Subtype.ext- Two elements of a subtype are equal if their underlying values are equal
Sym2.mem_and_mem_iff- For distinct elements x and y, both belong to an unordered pair z if and only if z is s(x, y)
Sym2.eq_swap- The unordered pair s(a, b) equals s(b, a)
Sym2.eq_iff.1- Two unordered pairs s(a, b) and s(c, d) are equal if and only if (a = c and b = d) or (a = d and b = c)
Sym2.mem_iff- An element belongs to s(a, b) if and only if it equals a or equals b
Sym2.mem_iff.1- If an element belongs to s(a, b), it is equal to a or equal to b
Sym2.mem_iff_exists.1- An element belongs to an unordered pair if and only if the pair can be written with that element as an endpoint
Sym2.mem_mk_left- An element x belongs to the unordered pair s(x, y)
Sym2.mem_mk_right- An element y belongs to the unordered pair s(x, y)
Sym2.mk_isDiag_iff.2- An unordered pair with identical endpoints is a diagonal (loop)
congrArg- Applying a function to equal inputs produces equal outputs
multigraph_cubic_third_edge- At any vertex of degree 3 with two distinct incident edges, there exists a unique third incident edge
truncation_local_state_internal_cover- In a cubic multigraph with six colours, any colour not used by the c-state at vertex v is the h-state of some incident edge
- The truncation graph T(G) has vertices representing ports (half-edges, formalized as pairs (v, e) with v ∈ ends(e)), so each multigraph vertex corresponds to a triangle of internal edges, while each multigraph edge corresponds to an external edge between its two ports.
- In the backward direction, the candidate edge-colouring χ is constructed noncomputably using Hilbert choice (Classical.epsilon) from a relation specifying the colours of external and internal edges.
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 truncation_local_states_strong_coloring_iff {V E Ω : Type*} [Fintype Ω] (hΩ : Fintype.card Ω = 6) (ends : E → Sym2 V) (hloop : ∀ e, ¬ (ends e).IsDiag) (hcubic : ∀ v, Set.ncard {e | v ∈ ends e} = 3) (c h : V → E → Ω) (hc : ∀ v e f, v ∈ ends e → v ∈ ends f → c v e = c v f → e = f) (hh : ∀ v e f, v ∈ ends e → v ∈ ends f → h v e = h v f → e = f) (hch : ∀ v e f, v ∈ ends e → v ∈ ends f → h v e ≠ c v f) : truncation_local_states_define_strong_coloring ends c h ↔ ∀ e u v, ends e = s(u, v) → c u e = c v e ∧ Disjoint (truncation_exposed_pair ends c h u e) (truncation_exposed_pair ends c h v e) := by classical have port_ext : ∀ p q : {p : V × E // p.1 ∈ ends p.2}, p.1.1 = q.1.1 → p.1.2 = q.1.2 → p = q := fun p q h1 h2 => Subtype.ext (Prod.ext h1 h2) have ends_eq : ∀ e u w, u ∈ ends e → w ∈ ends e → u ≠ w → ends e = s(u, w) := fun e u w hu hw hne => (Sym2.mem_and_mem_iff hne).1 ⟨hu, hw⟩ constructor · rintro ⟨χ, hs, hext, hint⟩ e u v huv have hu : u ∈ ends e := by rw [huv]; exact Sym2.mem_mk_left u v have hv : v ∈ ends e := by rw [huv]; exact Sym2.mem_mk_right u v have hne : u ≠ v := by intro h' apply hloop e rw [huv, h'] exact Sym2.mk_isDiag_iff.2 rfl let p : {p : V × E // p.1 ∈ ends p.2} := ⟨(u, e), hu⟩ let q : {p : V × E // p.1 ∈ ends p.2} := ⟨(v, e), hv⟩ have hpq : p ≠ q := fun h' => hne (congrArg (fun x : {p : V × E // p.1 ∈ ends p.2} => x.1.1) h') refine ⟨?_, ?_⟩ · have h1 : χ s(p, q) = c u e := hext p q hpq rfl have h2 : χ s(q, p) = c v e := hext q p hpq.symm rfl rw [Sym2.eq_swap] at h2 exact h1.symm.trans h2 · rw [Set.disjoint_left] rintro ω ⟨hωu, hωu'⟩ ⟨hωv, hωv'⟩ obtain ⟨g, hg, hgω⟩ := truncation_local_state_internal_cover hΩ hcubic hc hh hch hωu obtain ⟨g', hg', hgω'⟩ := truncation_local_state_internal_cover hΩ hcubic hc hh hch hωv have hge : g ≠ e := by rintro rfl; exact hωu' hgω.symm have hge' : g' ≠ e := by rintro rfl; exact hωv' hgω'.symm obtain ⟨k, hk, hke, hkg, -⟩ := multigraph_cubic_third_edge hcubic hu hg hge.symm obtain ⟨k', hk', hke', hkg', -⟩ := multigraph_cubic_third_edge hcubic hv hg' hge'.symm let a2 : {p : V × E // p.1 ∈ ends p.2} := ⟨(u, k), hk⟩ let r : {p : V × E // p.1 ∈ ends p.2} := ⟨(u, g), hg⟩ let b2 : {p : V × E // p.1 ∈ ends p.2} := ⟨(v, k'), hk'⟩ let r' : {p : V × E // p.1 ∈ ends p.2} := ⟨(v, g'), hg'⟩ have hpa2 : p ≠ a2 := fun h' => hke (congrArg (fun x : {p : V × E // p.1 ∈ ends p.2} => x.1.2) h').symm have hpr : p ≠ r := fun h' => hge (congrArg (fun x : {p : V × E // p.1 ∈ ends p.2} => x.1.2) h').symm have ha2r : a2 ≠ r := fun h' => hkg (congrArg (fun x : {p : V × E // p.1 ∈ ends p.2} => x.1.2) h') have hqb2 : q ≠ b2 := fun h' => hke' (congrArg (fun x : {p : V × E // p.1 ∈ ends p.2} => x.1.2) h').symm have hqr' : q ≠ r' := fun h' => hge' (congrArg (fun x : {p : V × E // p.1 ∈ ends p.2} => x.1.2) h').symm have hb2r' : b2 ≠ r' := fun h' => hkg' (congrArg (fun x : {p : V × E // p.1 ∈ ends p.2} => x.1.2) h') have hx : χ s(p, a2) = ω := by rw [← hgω]; exact hint p a2 r hpa2 hpr ha2r rfl rfl have hy : χ s(q, b2) = ω := by rw [← hgω']; exact hint q b2 r' hqb2 hqr' hb2r' rfl rfl refine hs s(p, a2) ((SimpleGraph.mem_edgeSet _).2 ⟨hpa2, Or.inl rfl⟩) s(q, b2) ((SimpleGraph.mem_edgeSet _).2 ⟨hqb2, Or.inl rfl⟩) ?_ (Or.inr ⟨p, q, Sym2.mem_mk_left _ _, Sym2.mem_mk_left _ _, ⟨hpq, Or.inr rfl⟩⟩) (hx.trans hy.symm) intro h' have hmem : p ∈ s(q, b2) := h' ▸ Sym2.mem_mk_left p a2 rcases Sym2.mem_iff.1 hmem with h'' | h'' · exact hne (congrArg (fun x : {p : V × E // p.1 ∈ ends p.2} => x.1.1) h'') · exact hne (congrArg (fun x : {p : V × E // p.1 ∈ ends p.2} => x.1.1) h'') · intro H have : Nonempty Ω := Fintype.card_pos_iff.mp (by omega) let Rel : Sym2 {p : V × E // p.1 ∈ ends p.2} → Ω → Prop := fun z ω => (∃ p q : {p : V × E // p.1 ∈ ends p.2}, z = s(p, q) ∧ p ≠ q ∧ p.1.2 = q.1.2 ∧ ω = c p.1.1 p.1.2) ∨ (∃ p q r : {p : V × E // p.1 ∈ ends p.2}, z = s(p, q) ∧ p ≠ q ∧ p ≠ r ∧ q ≠ r ∧ p.1.1 = q.1.1 ∧ p.1.1 = r.1.1 ∧ ω = h r.1.1 r.1.2) let χ : Sym2 {p : V × E // p.1 ∈ ends p.2} → Ω := fun z => Classical.epsilon (Rel z) have port_third : ∀ p q r r' : {p : V × E // p.1 ∈ ends p.2}, p ≠ q → p.1.1 = q.1.1 → r ≠ p → r ≠ q → r' ≠ p → r' ≠ q → r.1.1 = p.1.1 → r'.1.1 = p.1.1 → r = r' := by intro p q r r' hpq hv hrp hrq hr'p hr'q hr hr' have hpe : p.1.1 ∈ ends p.1.2 := p.2 have hqe : p.1.1 ∈ ends q.1.2 := by rw [hv]; exact q.2 have hef : p.1.2 ≠ q.1.2 := fun h' => hpq (port_ext p q hv h') obtain ⟨g, -, -, -, hall⟩ := multigraph_cubic_third_edge hcubic hpe hqe hef have hrg : r.1.2 = g := by have hre : p.1.1 ∈ ends r.1.2 := by rw [← hr]; exact r.2 rcases hall _ hre with h' | h' | h' · exact absurd (port_ext r p hr h') hrp · exact absurd (port_ext r q (hr.trans hv) h') hrq · exact h' have hr'g : r'.1.2 = g := by have hre : p.1.1 ∈ ends r'.1.2 := by rw [← hr']; exact r'.2 rcases hall _ hre with h' | h' | h' · exact absurd (port_ext r' p hr' h') hr'p · exact absurd (port_ext r' q (hr'.trans hv) h') hr'q · exact h' exact port_ext r r' (hr.trans hr'.symm) (hrg.trans hr'g.symm) have hext' : ∀ p q : {p : V × E // p.1 ∈ ends p.2}, p ≠ q → p.1.2 = q.1.2 → χ s(p, q) = c p.1.1 p.1.2 := by intro p q hpq he have hR : Rel s(p, q) (c p.1.1 p.1.2) := Or.inl ⟨p, q, rfl, hpq, he, rfl⟩ have hspec : Rel s(p, q) (χ s(p, q)) := Classical.epsilon_spec ⟨_, hR⟩ have hvne : p.1.1 ≠ q.1.1 := fun h' => hpq (port_ext p q h' he) rcases hspec with ⟨p', q', hz, hpq', he', hω⟩ | ⟨p', q', r', hz, hpq', hpr', hqr', hv1, hv2, hω⟩ · rw [hω] rcases Sym2.eq_iff.1 hz with ⟨h1, h2⟩ | ⟨h1, h2⟩ · rw [← h1] · rw [← h2, ← he] have hq : q.1.1 ∈ ends p.1.2 := by rw [he]; exact q.2 exact ((H p.1.2 p.1.1 q.1.1 (ends_eq _ _ _ p.2 hq hvne)).1).symm · exfalso have : p.1.1 = q.1.1 := by rcases Sym2.eq_iff.1 hz with ⟨h1, h2⟩ | ⟨h1, h2⟩ · rw [h1, h2]; exact hv1 · rw [h1, h2]; exact hv1.symm exact hvne this have hint' : ∀ p q r : {p : V × E // p.1 ∈ ends p.2}, p ≠ q → p ≠ r → q ≠ r → p.1.1 = q.1.1 → p.1.1 = r.1.1 → χ s(p, q) = h r.1.1 r.1.2 := by intro p q r hpq hpr hqr hv hvr have hR : Rel s(p, q) (h r.1.1 r.1.2) := Or.inr ⟨p, q, r, rfl, hpq, hpr, hqr, hv, hvr, rfl⟩ have hspec : Rel s(p, q) (χ s(p, q)) := Classical.epsilon_spec ⟨_, hR⟩ rcases hspec with ⟨p', q', hz, hpq', he', hω⟩ | ⟨p', q', r', hz, hpq', hpr', hqr', hv1, hv2, hω⟩ · exfalso have : p.1.2 = q.1.2 := by rcases Sym2.eq_iff.1 hz with ⟨h1, h2⟩ | ⟨h1, h2⟩ · rw [h1, h2]; exact he' · rw [h1, h2]; exact he'.symm exact hpq (port_ext p q hv this) · rw [hω] have key : r' ≠ p ∧ r' ≠ q ∧ r'.1.1 = p.1.1 := by rcases Sym2.eq_iff.1 hz with ⟨h1, h2⟩ | ⟨h1, h2⟩ · rw [h1, h2]; exact ⟨hpr'.symm, hqr'.symm, hv2.symm⟩ · rw [h1, h2]; exact ⟨hqr'.symm, hpr'.symm, hv2.symm.trans hv1⟩ have := port_third p q r' r hpq hv key.1 key.2.1 hpr.symm hqr.symm key.2.2 hvr.symm rw [this] refine ⟨χ, ?_, hext', hint'⟩ -- two internal edges at the same vertex with the same opposite port are equal have int_eq : ∀ a b a' b' r : {p : V × E // p.1 ∈ ends p.2}, a ≠ b → a' ≠ b' → a.1.1 = b.1.1 → a'.1.1 = b'.1.1 → a'.1.1 = a.1.1 → r ≠ a → r ≠ b → r ≠ a' → r ≠ b' → r.1.1 = a.1.1 → s(a, b) = s(a', b') := by intro a b a' b' r hab ha'b' hv hv' hw hra hrb hra' hrb' hr have ha' : a' = a ∨ a' = b := by by_contra hcon push Not at hcon exact hra' (port_third a b r a' hab hv hra hrb hcon.1 hcon.2 hr hw) have hb' : b' = a ∨ b' = b := by by_contra hcon push Not at hcon exact hrb' (port_third a b r b' hab hv hra hrb hcon.1 hcon.2 hr (hv'.symm.trans hw)) rcases ha' with rfl | rfl <;> rcases hb' with rfl | rfl <;> first | rfl | exact Sym2.eq_swap | exact absurd rfl ha'b' have ext_eq : ∀ a b b' : {p : V × E // p.1 ∈ ends p.2}, a ≠ b → a ≠ b' → a.1.2 = b.1.2 → a.1.2 = b'.1.2 → b = b' := by intro a b b' hab hab' hx hx' have hvne : a.1.1 ≠ b.1.1 := fun h' => hab (port_ext a b h' hx) have hvne' : a.1.1 ≠ b'.1.1 := fun h' => hab' (port_ext a b' h' hx') have hb : b'.1.1 ∈ ends a.1.2 := by rw [hx']; exact b'.2 have hb0 : b.1.1 ∈ ends a.1.2 := by rw [hx]; exact b.2 rw [ends_eq a.1.2 a.1.1 b.1.1 a.2 hb0 hvne, Sym2.mem_iff] at hb rcases hb with h' | h' · exact absurd h'.symm hvne' · exact port_ext b b' h'.symm (hx.symm.trans hx') -- the colour of an internal edge at `a` have int_col : ∀ a b : {p : V × E // p.1 ∈ ends p.2}, a ≠ b → a.1.1 = b.1.1 → ∃ g, a.1.1 ∈ ends g ∧ g ≠ a.1.2 ∧ g ≠ b.1.2 ∧ χ s(a, b) = h a.1.1 g := by intro a b hab hv have hb : a.1.1 ∈ ends b.1.2 := by rw [hv]; exact b.2 have hef : a.1.2 ≠ b.1.2 := fun h' => hab (port_ext a b hv h') obtain ⟨g, hg, hga, hgb, -⟩ := multigraph_cubic_third_edge hcubic a.2 hb hef refine ⟨g, hg, hga, hgb, ?_⟩ have hra : a ≠ ⟨(a.1.1, g), hg⟩ := fun h' => hga (congrArg (fun x : {p : V × E // p.1 ∈ ends p.2} => x.1.2) h').symm have hrb : b ≠ ⟨(a.1.1, g), hg⟩ := fun h' => hgb (congrArg (fun x : {p : V × E // p.1 ∈ ends p.2} => x.1.2) h').symm exact hint' a b ⟨(a.1.1, g), hg⟩ hab hra hrb hv rfl have around : ∀ a b a' b' : {p : V × E // p.1 ∈ ends p.2}, (multigraph_truncation ends).Adj a b → (multigraph_truncation ends).Adj a' b' → a.1.1 = a'.1.1 → s(a, b) ≠ s(a', b') → χ s(a, b) ≠ χ s(a', b') := by intro a b a' b' hab ha'b' hw hne heq obtain ⟨hab1, hab2⟩ := hab obtain ⟨ha'b'1, ha'b'2⟩ := ha'b' rcases hab2 with hi | hx <;> rcases ha'b'2 with hi' | hx' · obtain ⟨g, hg, hga, hgb, hcol⟩ := int_col a b hab1 hi obtain ⟨g', hg', hga', hgb', hcol'⟩ := int_col a' b' ha'b'1 hi' rw [hcol, hcol', ← hw] at heq have hg'' : a.1.1 ∈ ends g' := by rw [hw]; exact hg' have hgg : g = g' := hh _ _ _ hg hg'' heq subst hgg refine hne (int_eq a b a' b' ⟨(a.1.1, g), hg⟩ hab1 ha'b'1 hi hi' hw.symm ?_ ?_ ?_ ?_ rfl) · exact fun h' => hga (congrArg (fun x : {p : V × E // p.1 ∈ ends p.2} => x.1.2) h') · exact fun h' => hgb (congrArg (fun x : {p : V × E // p.1 ∈ ends p.2} => x.1.2) h') · exact fun h' => hga' (congrArg (fun x : {p : V × E // p.1 ∈ ends p.2} => x.1.2) h') · exact fun h' => hgb' (congrArg (fun x : {p : V × E // p.1 ∈ ends p.2} => x.1.2) h') · obtain ⟨g, hg, -, -, hcol⟩ := int_col a b hab1 hi rw [hcol, hext' a' b' ha'b'1 hx', ← hw] at heq have ha'e : a.1.1 ∈ ends a'.1.2 := by rw [hw]; exact a'.2 exact hch _ _ _ hg ha'e heq · obtain ⟨g', hg', -, -, hcol'⟩ := int_col a' b' ha'b'1 hi' rw [hext' a b hab1 hx, hcol', ← hw] at heq have hg'' : a.1.1 ∈ ends g' := by rw [hw]; exact hg' exact hch _ _ _ hg'' a.2 heq.symm · rw [hext' a b hab1 hx, hext' a' b' ha'b'1 hx', ← hw] at heq have ha'e : a.1.1 ∈ ends a'.1.2 := by rw [hw]; exact a'.2 have hee : a.1.2 = a'.1.2 := hc _ _ _ a.2 ha'e heq have haa : a = a' := port_ext a a' hw hee subst haa exact hne (by rw [ext_eq a b b' hab1 ha'b'1 hx hx']) have around2 : ∀ x y : Sym2 {p : V × E // p.1 ∈ ends p.2}, x ∈ (multigraph_truncation ends).edgeSet → y ∈ (multigraph_truncation ends).edgeSet → x ≠ y → ∀ z z', z ∈ x → z' ∈ y → z.1.1 = z'.1.1 → χ x ≠ χ y := by intro x y hx hy hxy z z' hz hz' hzz obtain ⟨b, rfl⟩ := Sym2.mem_iff_exists.1 hz obtain ⟨b', rfl⟩ := Sym2.mem_iff_exists.1 hz' exact around z b z' b' ((SimpleGraph.mem_edgeSet _).1 hx) ((SimpleGraph.mem_edgeSet _).1 hy) hzz hxy intro x hx y hy hxy hconf rcases hconf with ⟨z, hz1, hz2⟩ | ⟨u, w, hu, hw, huw⟩ · exact around2 x y hx hy hxy z z hz1 hz2 rfl · obtain ⟨huw1, huw2⟩ := huw rcases huw2 with hv | he · exact around2 x y hx hy hxy u w hu hw hv · obtain ⟨u2, rfl⟩ := Sym2.mem_iff_exists.1 hu obtain ⟨w2, rfl⟩ := Sym2.mem_iff_exists.1 hw have hadj := (SimpleGraph.mem_edgeSet _).1 hx have hadj' := (SimpleGraph.mem_edgeSet _).1 hy have hvne : u.1.1 ≠ w.1.1 := fun h' => huw1 (port_ext u w h' he) by_cases hx2 : u.1.1 = u2.1.1 · by_cases hy2 : w.1.1 = w2.1.1 · obtain ⟨g, hg, hgu, -, hcol⟩ := int_col u u2 hadj.1 hx2 obtain ⟨g', hg', hgw, -, hcol'⟩ := int_col w w2 hadj'.1 hy2 have hwe : w.1.1 ∈ ends u.1.2 := by rw [he]; exact w.2 have hdisj := (H u.1.2 u.1.1 w.1.1 (ends_eq _ _ _ u.2 hwe hvne)).2 have m1 : χ s(u, u2) ∈ truncation_exposed_pair ends c h u.1.1 u.1.2 := by rw [hcol] exact ⟨fun f hf => (hch _ _ _ hg hf).symm, fun h' => hgu (hh _ _ _ hg u.2 h')⟩ have m2 : χ s(w, w2) ∈ truncation_exposed_pair ends c h w.1.1 u.1.2 := by rw [hcol', he] exact ⟨fun f hf => (hch _ _ _ hg' hf).symm, fun h' => hgw (hh _ _ _ hg' w.2 h')⟩ intro heq rw [heq] at m1 exact Set.disjoint_left.1 hdisj m1 m2 · -- `s(w, w2)` is external, so `w2 = u` have hw2 : w.1.2 = w2.1.2 := hadj'.2.resolve_left hy2 have hwu : w ≠ u := fun h' => huw1 h'.symm have : w2 = u := ext_eq w w2 u hadj'.1 hwu hw2 he.symm subst this exact around2 _ _ hx hy hxy w2 w2 (Sym2.mem_mk_left _ _) (Sym2.mem_mk_right _ _) rfl · have hu2 : u.1.2 = u2.1.2 := hadj.2.resolve_left hx2 have : u2 = w := ext_eq u u2 w hadj.1 huw1 hu2 he subst this exact around2 _ _ hx hy hxy u2 u2 (Sym2.mem_mk_right _ _) (Sym2.mem_mk_left _ _) rfl