Suggest a Book

# 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.
Level:
Source: folklore
delete retag edit

Shiva Kintali
691 1 6 25
http://www.cs.princeton.e...
POST AN EXERCISE POST A VIDEO POST NOTES POST MULTIPLE-CHOICE QUESTION

## Stats

Posted: Aug 07 '12

Seen: 107 times

Last updated: Aug 12 '12