simple_graph_triangle_packing_number
def
ν(G): the maximum number of pairwise edge-disjoint triangles of G (two triangles are edge-disjoint when they share at most one vertex).
Statement
noncomputable def simple_graph_triangle_packing_number {V : Type*} [DecidableEq V] (G : SimpleGraph V) : ℕ
- Defined in
- arXiv:2610.15539 (Tuza's conjecture under an edge-count condition), Sec. 1 (ν(G), the triangle packing number).
- Verified
- 14 Oct 2026
- Axioms
- none listed
- Used by 63
- 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_packing_number_le_delete_edge_add_oneDeleting an edge e from G decreases the triangle packing number by at most 1: ν(G) ≤ ν(G \ {e}) + 1.
- simple_graph_pair_stable_k4_link_two_attachment_sharpA two-edge-stable graph can contain a four-clique and a distinguished clique vertex for which one face vertex has no external common…
- in715_deficit_p_sizeFinite certificate for the explicit fourteen-vertex graph.
- 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_packing_number_induce_leThe triangle packing number of an induced subgraph is at most that of the whole graph.
- 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_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_in693_ten_seed_pair_stableDeleting any two distinct edges of the ten-vertex seed leaves its triangle packing number equal to eight.
- in715_deficit_preciseAn explicit fourteen-vertex graph has a maximum seven-triangle packing, a seven-edge triangle cover, an outside five-cycle link and a…
- simple_graph_maximum_packing_fixed_two_budget_counterexampleA nine-vertex graph has a maximum triangle packing with at most one singleton-forced edge per packed triangle, but no triangle cover…
- 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_pair_stable_active_vertex_at_least_five_trianglesIn a finite graph whose maximum triangle-packing number survives every two-edge deletion, any vertex that lies in a triangle lies in at…
- simple_graph_maximum_packing_outside_induced_kernelThe support of a maximum packing plus one vertex has at most three times the packing size plus one vertices and contains every triangle…
- 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_packing_number_monoTriangle packing number is monotone under subgraph inclusion: if H ≤ G, then ν(H) ≤ ν(G).
- simple_graph_external_k4_private_pair_decreases_packingLet P be a maximum edge-disjoint triangle packing containing abc, and let a and b occur in no other triangle of P. If x lies outside the…
- simple_graph_triangle_packing_number_ge_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_unrestricted_singleton_witness_edge_union_counterexampleThe unrestricted witness-edge union does not satisfy the proposed sunflower forced-base half-independence statement: the explicitly…
- simple_graph_triangle_outside_maximum_packing_card_le_oneEvery triangle in G shares an edge with any maximum packing, so it has at most one vertex outside the packing support.
- simple_graph_pair_stable_vertex_link_not_four_cycleIn a two-edge-stable graph, the graph induced by the neighborhood of any vertex cannot be exactly a four-cycle after isolated vertices are…
- simple_graph_stable_disjoint_edges_outside_packing_incompatible_exampleThere is a stable graph of triangle packing number three, a maximum packing P, and a five-edge triangle cover containing two…
- 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_pair_stable_support_max_outside_link_card_le_packingFor a support-maximal maximum triangle packing in a two-edge-stable graph, an outside vertex has at most one link edge per packed…
- in715_deficit_pack_eqFinite certificate for the explicit fourteen-vertex graph.
- simple_graph_pair_stable_private_k4_packing_incidenceLet a maximum packing in a two-edge-stable graph contain abc, with a and b private to that packing triangle. If abcx is a four-clique…
- simple_graph_maximum_packing_private_k4_edge_codegree_twoIf a triangle in a maximum edge-disjoint triangle packing has two vertices private to that triangle and extends to a four-clique whose…
- simple_graph_stable_two_packing_arbitrary_cover_counterexampleThere is a finite edge-deletion-stable graph with triangle packing number two, a maximum packing P, and a four-edge triangle cover C such…
- simple_graph_support_max_packing_external_k4_decreases_packingIf a maximum triangle packing has maximum vertex support, a packed face abc and an outside fourth vertex x spanning a four-clique force…
- simple_graph_triangle_packing_number_induce_eq_of_packing_subsetIf a subset S contains all vertices of a maximum packing of triangles in G, then the triangle packing number of the induced subgraph G[S]…
- simple_graph_triangle_packing_number_delete_edge_lt_or_eqFor every finite graph G, either some single-edge deletion strictly decreases the triangle packing number, or every single-edge deletion…
- simple_graph_pair_stable_outside_kernel_five_trianglesIn a two-edge-stable graph, every active vertex that lies in the support-plus-one-vertex kernel and outside a maximum packing supported in…
- 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_maximum_triangle_packing_edge_meetsEvery triangle shares an edge with a member of a maximum edge-disjoint triangle packing.
- 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_free_pair_stable_nonbipartite_exampleA triangle-free two-edge-stable graph can fail to be bipartite; its empty packing is maximum and support-maximal.
- simple_graph_opposite_pair_stable_k4_attachmentLet P be a maximum edge-disjoint triangle packing containing abc, and let x complete abc to a four-clique. Suppose neither ax nor bx is an…
- simple_graph_pair_stable_support_max_incidence_two_bad_packing_counterexampleThere is an eight-vertex two-edge-stable graph with a maximum triangle packing covering every vertex, in which every vertex belongs to at…
- simple_graph_stable_triangle_not_in_maximum_packing_exampleThere is a finite graph with triangle packing number two in which every edge deletion preserves the packing number, but some triangle…
- simple_graph_stable_unforced_anchor_ten_exampleA two-edge-stable graph has a full-support maximum packing with a fully forced K4 face whose internal anchor lies only in unforced packed…
- simple_graph_support_max_packing_outside_swap_privateIf P has maximum vertex support among triangle packings of its size, replacing packed triangle abc by abx with x outside P is possible…
- simple_graph_triangle_packing_number_eq_zero_of_clique_freeA triangle-free graph has triangle packing number 0.
- simple_graph_maximum_packing_outside_triangles_inside_supportEvery triangle through a vertex outside a maximum triangle packing lies in that vertex together with the packing support.
- simple_graph_exists_support_maximum_triangle_packingEvery finite graph has a maximum triangle packing whose vertex support has maximum cardinality among all maximum triangle packings.
- 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_packing_decreases_of_high_codegreeDeleting an edge with more than twice the maximum triangle packing number common neighbors strictly decreases the packing number.
- simple_graph_in693_ten_seed_packing_numberThe concrete ten-vertex five-link seed has triangle packing number eight.
- simple_graph_pair_stable_vertex_link_edge_spoke_exchangeIn a two-edge-stable graph, for every edge yz of the link at x and every neighbor w of x, another link edge meets yz and avoids w.
- simple_graph_deficit_two_example_two_edge_dropDeleting two specified base edges from the explicit 14-vertex local-count counterexample decreases its triangle-packing number from seven…
- in701_packing_le_edge_coverA triangle packing has at most as many triangles as an edge cover.
- 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_pair_stable_support_max_k4_anchor_internalIn a two-edge-stable graph, every fourth vertex completing a packed triangle of a support-maximal maximum triangle packing to a…
- 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_maximum_packing_two_forced_edges_k4For a maximum triangle packing, if a packed triangle has two singleton-forced edges then its three vertices have a common fourth vertex…
- simple_graph_pair_stable_kernel_link_edge_spoke_exchangeFor an active outside vertex of a maximum packing supported in a support-plus-one-vertex kernel, the local edge/spoke exchange guaranteed…
- simple_graph_stable_triangle_active_edge_in_maximum_packingIn a finite graph where deleting any edge preserves the maximum triangle packing number, every edge belonging to a triangle is used by…
- 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.
- simple_graph_pair_stable_triangle_active_incidence_two_unpacked_nonbipartiteThere is a triangle-active two-edge-stable eight-vertex graph with a support-maximal maximum triangle packing in which every vertex is in…
Lean source view module on GitHub
/-- `ν(G)`: the maximum number of pairwise edge-disjoint triangles of `G`. -/ noncomputable def simple_graph_triangle_packing_number {V : Type*} [DecidableEq V] (G : SimpleGraph V) : ℕ := sSup {n | ∃ T : Finset (Finset V), (∀ t ∈ T, G.IsNClique 3 t) ∧ (T : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1) ∧ T.card = n}