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

1. Reminder: (G) denotes the minimum size of a vertex cover of G, and (G) denotes the maximum size of a matching in G. a) State Knig's theorem, relating these two parameters. [2 points] b) Find (G) and (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)20. [5 points]