simple_graph_is_color_connecting
def
Let γ be an edge colouring of a graph G. A set W of edges of G is colour-connecting if, for every colour c used by γ, the spanning subgraph whose edges are the edges of colour c together with W is connected.
Statement
def simple_graph_is_color_connecting {V α : Type*} (G : SimpleGraph V) (γ : G.edgeSet → α) (W : Set (Sym2 V)) : Prop
- Defined in
- arXiv:2610.22142 (Wild number for spanning trees in complete and complete bipartite graphs), Sec. 2 (definition of a color-connecting set; every colouring is taken surjective, so the colours are the colours of edges).
- Verified
- 16 Oct 2026
- Axioms
- none listed
- Used by 17
- simple_graph_wild_number_le_of_is_color_connectingThe wild number is at most the size of any colour-connecting set.
- wild_odd_optimal_color_connecting_partitionAt odd order n>=3, every color-connecting edge set of size n-floor(n/3) in a proper complete-graph edge coloring yields a rooted partition…
- wild_color_connecting_crosses_closed_cutFor a color-connecting edge set W, every nonempty proper vertex set closed under a used color has a W edge crossing to its complement.
- wild_number_complete_graph_two_coloring_rangeLet n ≥ 4. Every (surjective) 2-edge-colouring of K_n has wild number at most n − 2, and every integer 0 ≤ k ≤ n − 2 is the wild number of…
- simple_graph_is_color_connecting_edge_setIn a connected edge-coloured graph, the whole edge set is colour-connecting.
- simple_graph_is_color_connecting_monoA set of edges containing a colour-connecting set is colour-connecting.
- simple_graph_wild_number_le_card_edge_finsetThe wild number of a finite connected edge-coloured graph is at most its number of edges.
- wild_number_complete_bipartite_min_proper_coloringLet 2 ≤ m ≤ n. For every proper edge colouring of the complete bipartite graph K_{m,n} with n colours (these are exactly its minimum…
- wild_number_complete_odd_eq_iff_optimal_partitionFor every minimum proper coloring of K_n at odd order n>=3, its wild number equals floor(4*ceil(n/2)/3) if and only if there is a rooted…
- simple_graph_wild_number_attainedFor any finite connected edge-colored graph, some finite color-connecting edge set has cardinality exactly its wild number.
- quadripartite_exists_wild_number_eq_of_upper_exclusionIf every proper 3n-edge-colouring of K_{n,n,n,n} has wild number at most 2n + 1, and some colouring has no colour-connecting set of at…
- wild_block_cut_of_color_connectingA rooted vertex partition whose blocks contain both endpoints of every wild edge has an edge of every used color across every nonempty…
- wild_number_complete_graph_le_sub_oneFor every n ≥ 1 and every edge colouring γ of K_n, wld_γ(K_n) ≤ n − 1 (a spanning star is colour-connecting).
- wild_number_complete_graph_min_proper_coloring_geLet n ≥ 3 and let ρ be a minimum proper edge colouring of K_n (a proper colouring with χ'(K_n) colours). Then wld_ρ(K_n) ≥ ⌊4⌈n/2⌉/3⌋.
- wild_odd_color_connecting_closed_block_card_ge_threeIn a proper complete-graph edge coloring at odd order n>=3, every nonempty vertex block with no wild edge crossing its boundary has at…
- simple_graph_wild_numberThe wild number wld_γ(G) of an edge-coloured graph is the minimum size of a colour-connecting set of edges.
- simple_graph_wild_number_le_of_block_cut_conditionLet a nonempty complete graph have a vertex-to-block map p and one root r(i) in each of q blocks. If every used color has an edge crossing…
Lean source view module on GitHub
/-- `W` is a colour-connecting set of the edge colouring `γ` of `G`: `W ⊆ E(G)` and, for every colour class, the class together with `W` spans a connected graph (colours are those of edges, so the colouring is read as surjective onto its used colours). -/ def simple_graph_is_color_connecting {V α : Type*} (G : SimpleGraph V) (γ : G.edgeSet → α) (W : Set (Sym2 V)) : Prop := W ⊆ G.edgeSet ∧ ∀ e : G.edgeSet, (SimpleGraph.fromEdgeSet ({f | ∃ hf : f ∈ G.edgeSet, γ ⟨f, hf⟩ = γ e} ∪ W)).Connected