is_type_ii_edge
An edge uv of a simple graph G is a type II edge with parameter k if u is adjacent to v, there exists a good set S for uv of cardinality k + 1, every good set for uv has cardinality at least k + 1, and for every good set S of cardinality k + 1, the graph (G - uv)[Sᶜ] has exactly 3 connected components, and the connected components containing u and v have supports equal to the singletons {u} and {v} respectively.
Statement
def is_type_ii_edge {V : Type*} [Fintype V] (G : SimpleGraph V) (u v : V) (k : ℕ) : Prop
- Defined in
- arXiv:2611.09072, Lemma 2.8(ii)
- Verified
- 09 Nov 2026
- Axioms
- none listed
- Built on 1
- is_good_set_for_edgeFor vertices u and v, a finite subset S disjoint from {u, v} is a good set for the edge uv with parameter k if |S| ≥ k, the number of odd…
Read back from the Lean
Let V be a finite type, G be a simple graph on V, u, v : V, and k : ℕ.
The predicate is_type_ii_edge G u v k asserts that all of the following hold:
1. u and v are adjacent in G (G.Adj u v);
2. There exists a finset S : Finset V such that S is a good set for the edge (u, v) with respect to k (is_good_set_for_edge G u v S k) and |S| = k + 1;
3. For every finset S : Finset V, if S is a good set for (u, v) with respect to k, then |S| ≥ k + 1 (meaning the minimum cardinality of any good set is k + 1);
4. For every finset S : Finset V, if S is a good set for (u, v) with respect to k and |S| = k + 1, then (since u ∉ S and v ∉ S), in the subgraph H of G induced on the complement V \ S after removing the edge {u, v}:
- H has exactly 3 connected components (Nat.card H.ConnectedComponent = 3);
- The connected component containing u in H consists solely of {u} (i.e., its vertex support is {⟨u, hu⟩});
- The connected component containing v in H consists solely of {v} (i.e., its vertex support is {⟨v, hv⟩}).
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
/-- An edge uv in G is a type II edge with parameter k if G.Adj u v, the minimum cardinality of any good set is k + 1, and every good set of cardinality k + 1 separates G - uv into 3 components, two being singletons {u} and {v}. -/ def is_type_ii_edge {V : Type*} [Fintype V] (G : SimpleGraph V) (u v : V) (k : ℕ) : Prop := G.Adj u v ∧ (∃ S : Finset V, is_good_set_for_edge G u v S k ∧ S.card = k + 1) ∧ (∀ S : Finset V, is_good_set_for_edge G u v S k → k + 1 ≤ S.card) ∧ (∀ S : Finset V, is_good_set_for_edge G u v S k → S.card = k + 1 → ∃ (hu : u ∉ S) (hv : v ∉ S), let H := (G.deleteEdges {s(u, v)}).induce (S : Set V)ᶜ Nat.card H.ConnectedComponent = 3 ∧ (H.connectedComponentMk ⟨u, hu⟩).supp = {⟨u, hu⟩} ∧ (H.connectedComponentMk ⟨v, hv⟩).supp = {⟨v, hv⟩})