Kőnig's theorem

Kőnig's theorem

Introduction

In this chapter we will consider König's theorem in graph theory and see how it can help us in solving problems.

Statement of König's Theorem

We all know what a matching is in graph theory. Let us consider one more concept — vertex cover (in particular, a minimum vertex cover).

Vertex Cover

A vertex cover in a graph $G$ is a subset of vertices

such that every edge $e \in E$ is incident to at least one vertex from $S$
(that is, the edge is covered).

A minimum vertex cover is a vertex cover of minimum size.

Statement of König's Theorem

Let be a bipartite graph.