Gallai Identities

Consider the following parameters of an undirected graph $G$ on $n$ vertices.

• $\nu(G)$ is the size of a maximum matching of $G$.
• $\tau(G)$ is the size of a minimum vertex cover of $G$.
• $\alpha(G)$ is the size of a maximum independent set in $G$.
• $\rho(G)$ is the size of a minimum edge cover of $G$.

Prove the following :

• $\nu(G) \leq \tau(G)$
• $\alpha(G) + \tau(G) = n$
• $\nu(G) + \rho(G) = n$

Prove the following when $G$ is a bipartite graph :

• $\nu(G) = \tau(G)$
• $\rho(G) = \alpha(G)$ and hence conclude that the complement of a bipartite graph is perfect.