A Bounded Diameter Strengthening of Kőnig’s Theorem

Kőnig’s theorem says that the vertex cover number of every bipartite graph is at most its matching number (in fact they are equal since, trivially, the matching number is at most the vertex cover number). An equivalent formulation of Kőnig’s theorem is that in every 2-coloring of the edges of a graph [Formula: see text], the number of monochromatic components needed to cover the vertex set of [Formula: see text] is at most the independence number of [Formula: see text]. We prove the following strengthening of Kőnig’s theorem: In every 2-coloring of the edges of a graph [Formula: see text], the number of monochromatic subgraphs of bounded diameter needed to cover the vertex set of [Formula: see text] is at most the independence number of [Formula: see text].