simple_graph_triangle_cover_number
def
τ(G): the minimum number of edges of G such that every triangle of G contains one of them.
Statement
noncomputable def simple_graph_triangle_cover_number {V : Type*} (G : SimpleGraph V) : ℕ
- Defined in
- arXiv:2610.15539 (Tuza's conjecture under an edge-count condition), Sec. 1 (τ(G), the triangle cover number).
- Verified
- 14 Oct 2026
- Axioms
- none listed
- Used by 24
- simple_graph_triangle_cover_of_avoided_near_high_codegreeIf a maximum triangle packing avoids an edge with at least twice the packing number minus one common neighbors and the packing number is…
- simple_graph_triangle_cover_number_eq_zero_of_clique_freeA triangle-free graph has triangle cover number 0.
- simple_graph_triangle_cover_number_le_two_of_packing_number_le_oneTuza's conjecture holds for graphs with packing number at most 1: if ν(G) ≤ 1, then τ(G) ≤ 2.
- simple_graph_triangle_cover_number_le_three_mul_packing_numberEvery finite graph satisfies τ(G) ≤ 3ν(G): the edges of a maximum family of edge-disjoint triangles meet every triangle.
- simple_graph_triangle_cover_number_le_packing_number_of_pairwise_edge_disjoint_trianglesIf any two distinct triangles of a finite graph G share at most one vertex (equivalently, no edge lies in two triangles), then τ(G) ≤…
- simple_graph_triangle_cover_number_monoTriangle cover number is monotone under subgraph inclusion: if H ≤ G, then τ(H) ≤ τ(G).
- simple_graph_triangle_cover_of_full_common_matchingIf an edge common-neighbor graph has a matching as large as the graph triangle packing number, the triangle cover number is at most the…
- simple_graph_edge_reduction_inequalityLet G be a finite simple graph. Suppose there exist a nonempty edge set F ⊆ E(G), a set S of pairwise edge-disjoint triangles of G, and an…
- simple_graph_triangle_cover_number_induce_leThe triangle cover number of an induced subgraph does not exceed that of the host graph.
- simple_graph_complete_no_small_vertex_triangle_reductionIn a complete graph, a nonempty vertex set of size at most one forty-first of the order cannot satisfy the standard vertex packing-cover…
- simple_graph_triangle_cover_number_delete_edge_leDeleting an edge e from G decreases the triangle cover number by at most 1: τ(G) ≤ τ(G \ {e}) + 1.
- simple_graph_stable_lex_private_triangle_direct_exchange_counterexampleThere is a stable graph with a unique minimum triangle edge cover and a maximum packing such that the cover has exactly one edge outside…
- simple_graph_triangle_cover_number_le_two_mul_packing_number_of_packing_critical_caseTuza's conjecture follows from its packing-critical case: if every finite graph G with 2 ≤ ν(G) in which every edge deletion preserves ν…
- simple_graph_triangle_cover_of_unique_triangle_edgeIf an edge belongs to exactly one triangle, then the triangle cover-packing inequality for the graph obtained by deleting the other two…
- simple_graph_triangle_cover_of_near_full_common_matchingIf an edge has a common-neighbor matching of size one below the graph triangle packing number and another common neighbor outside the…
- simple_graph_stable_lex_outside_forces_triangle_exampleThere is an edge-stable eight-vertex graph and maximum triangle packing P such that every minimum triangle cover minimizing its outside-P…
- simple_graph_triangle_cover_number_le_of_edge_reductionLet G be a finite simple graph, F a nonempty edge subset, S a pairwise edge-disjoint triangle family, and X an edge subset such that X…
- simple_graph_lex_cover_private_triangle_not_extendable_exampleThere is a stable graph with triangle packing number two, a maximum packing P, and a minimum triangle cover C minimizing its edges outside…
- simple_graph_triangle_cover_of_two_star_packingsTwo triangle-maximal families whose non-star edges lie in C give a triangle cover of size at most |C|+1 if their star centers are adjacent.
- simple_graph_triangle_cover_reduces_to_separator_freeGiven the two-vertex separator induction step, the triangle packing-cover inequality for all separator-free finite graphs implies it for…
- simple_graph_triangle_cover_number_le_two_mul_packing_of_local_certificateLet H be a subgraph of a finite graph G. If a triangle packing S in G is edge-disjoint from every triangle in H, and an edge set X of size…
- simple_graph_triangle_cover_number_le_two_mul_packing_number_of_decreasing_edgeInduction step for the easy branch: if every graph on the same vertex type with strictly smaller triangle packing number satisfies τ ≤ 2ν,…
- simple_graph_triangle_cover_number_le_two_mul_packing_of_uniform_local_reductionsIf every finite graph containing a triangle has a proper subgraph and a local packing-cover certificate that extends every packing of that…
- simple_graph_triangle_cover_number_eq_zero_of_packing_number_eq_zeroIf a finite graph has packing number 0, then its triangle cover number is 0.
Lean source view module on GitHub
/-- `τ(G)`: the minimum number of edges of `G` meeting every triangle of `G`. -/ noncomputable def simple_graph_triangle_cover_number {V : Type*} (G : SimpleGraph V) : ℕ := sInf {n | ∃ F : Finset (Sym2 V), (∀ e ∈ F, e ∈ G.edgeSet) ∧ (∀ t : Finset V, G.IsNClique 3 t → ∃ e ∈ F, ∀ x ∈ e, x ∈ t) ∧ F.card = n}