Benjamin Hackl @behackl.dev · Nov 19 Currently preparing tomorrows lecture on matchings in graphs, feat. Kőnig's theorem: In any bipartite graph, the size of a largest matching (blue; edges w/o shared endpoints) coincides with the size of a smallest vertex cover (red; vertices s.t. each edge has at least one endpoint covered).
5 likes 1 replies
?
Replies
... found this fun and short (but pretty dense) proof for it: core.ac.uk/download/pdf... Idea: use minimal counterexample, canonically produce smaller graphs and lift minimal covers from smaller graph to counterexample => ⚠️⚡ #mathsky