[Math] Gallai’s theorem on independent edges

combinatoricsgraph theory

In a simple graph of $n$ vertices let

$\alpha(G)$:
the maximal number of independent vertices (no two of them have a common edge) vertices

$\beta(G)$: the minimal number of covering vertices (edges from these vertices cover are all the edges)

$\gamma(G)$:the maximal number of independent edges (no two edges share the same point)

$\delta(G)$:the minimal number of covering edges (vertices on these edges are all the vertices)

It's straightforward to prove the following results:

$\gamma(G)\le\beta(G)$

$\alpha(G)\le\delta(G)$

We called the following Gallai's theorems:

$\alpha(G)+\beta(G)=n$

$\gamma(G)+\delta(G)=n$ (if the graph has no isolated points)

Could you help me prove these? When I try searching for Gallai's theorem, it only gives the Erdos-Gallai which is not this.

Best Answer

The first section of this PDF contains a proof of the result.

Related Question