Use the following notation (G) is the maximum size of an independent set of vertices (no edges among the vertices), 1(G) is the maximum size of a

Use the following notation α(G) is the maximum size of an independent set of vertices (no edges among the vertices), α1(G) is the maximum size of a matching (independent set of edges, β(G) is the minimum size of a vertex cover of edges (set of vertices such that each edge has at least one end in the set), β1(G) is the minimum size of an edge cover of vertices (set of edges such that every vertex is an end of at least one of the edges). The Konig-Egevary Theorem states that for bipartite graphs α1(G) = β(G). Our aim is to use this and parts (i) and (ii) below to prove that for bipartite graphs we also have α(G) = β1(G), the maximum size of an independent set of vertices equals the minimum number of edges needed to cover the vertices. (We need also to assume the are no isolated vertices, that is no vertices with degree 0 as they are not an end of any edge.) we can do this in 3 steps. Here n is the number of vertices and for (i) and (ii) the result is for any graph, not necessarily bipartite. (i) For any graph, prove the lemma that α(G) + β(G) = n. (ii) For any graph without isolated vertices, prove that α1(G) + β1(G) = n. (iii) Prove that for any bipartite graph without isolated vertices α(G) = β1(G). Hints: (i) is very short. Consider a maximum independent set S, its complement and where edges can be relative to S. (ii) Take a maximum matching and construct an cover by adding edges to cover unsaturated vertices arbitrarily. The size gives a bound on β1(G) in terms of n and α1(G). Then consider a minimum edge cover and show that it is a disjoint union of stars (complete bipartite graphs K1,t). Take an edge from each of these stars to form a matching. This gives a bound on α1(G) in terms of n and α1(G). Combine these to get (ii).