Sesión Matemática DiscretaA new elemental proof of K\H{o}nig's Theorem
Kevin D. Pereyra
Universidad Nacional de San Luis, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
The well-known K\H{o}nig's Theorem states that in a bipartite graph $G$, the number of edges in a maximum matching is equal to the number of vertices in a minimum vertex cover, i.e., $\mu(G)=\tau_{0}(G)$, see [1] and [2]. From this result, it is easy to deduce that if $e$ is an edge of $G$ connecting two vertices in a minimum vertex cover, then $G$ and $G-e$ have the same number of vertices in a minimum vertex cover, i.e., $\tau_{0}(G)=\tau_{0}(G-e)$. We present an elementary proof of this property without using K\H{o}nig's Theorem. Then we give a proof of K\H{o}nig's Theorem using this property. We also give an edge version of the property.
Trabajo en conjunto con: Daniel A. Jaume (Universidad Nacional de San Luis - IMASL - CONICET).
Referencias
[1] K\H{o}nig, Dénes. "Graphs and matrices." Matematikai és Fizikai Lapok 38 (1931): 116-119.
[2] Reichmeider, Philip Francis. The Equivalence of Some Combinatorial Matching Theorems. Adelphi University, 1978.