The Erdős-Gallai-Tuza conjecture asserts that, for every simple graph
on vertices,
where
is the largest size of a set of edges
containing at most one graph edge from each triangle,
and
is the smallest number of edges meeting every triangle
(Erdős et al. 1996).
Norin and Sun (2016) proved the stronger inequality obtained by replacing with the minimum number of edges
whose deletion makes bipartite. Such a deletion
destroys every triangle, so the stronger bound
implies the conjecture.
on 
vertices,
is the largest size of a set of edges
containing at most one graph edge from each triangle,
and 
is the smallest number of edges meeting every triangle
(Erdős et al. 1996).
with the minimum number of edges
whose deletion makes 
bipartite. Such a deletion
destroys every triangle, so the stronger bound
implies the conjecture.
