Reminder:

\\\\tau (G)

denotes the minimum size of a vertex cover of

G

, and

\ u (G)

denotes the maximum size of a matching in

G

.\ a) State Knig's theorem, relating these two parameters. [2 points]\ b) Find

\ u (G)

and

\\\\tau (vec(G))

in the graph

G

on the figure above. [3 points]\ c) Let

G

be a bipartite graph with bipartition

(A,B)

such that

|A|=|B|=5

. Suppose that

G

does not have a perfect matching. Show that

|E(G)|

. [5 points