In 1975 Lovász conjectured that every r-partite, r-uniform hypergraph contains \(r-1\) vertices whose deletion reduces the matching number. If true, this statement would imply a well-known conjecture of Ryser from 1971, which states that every r-partite, r-uniform hypergraph has a vertex cover of size at most \(r-1\) times its matching number. When \(r=2\) , Ryser’s conjecture is simply Kőnig’s theorem, and the conjecture of Lovász is an immediate corollary. Ryser’s conjecture for \(r=3\) was proven by Aharoni in 2001, and remains open for all \(r\ge 4\) . Here we show that the conjecture of Lovász is false in the case \(r=3\) . Our counterexample is the line hypergraph of the Biggs-Smith graph, a highly symmetric cubic graph on 102 vertices.
