with n-|M| colors, which by the perfection of complements of bipartite graphs corresponds to an independent set in G with n-|M| vertices, which corresponds to a vertex cover of G with M vertices. Conversely, Kőnig's theorem proves the perfection of the complements of bipartite graphs, a result proven in a more explicit form by . One can also connect Kőnig's line coloring theorem to a different class of perfect graphs, the line graphs of bipartite graphs. If G is a graph, the line graph L(G) has a vertex for each edge of G, and an edge for each pair of adjacent edges in G. Thus, the chromatic number of L(G) equals the chromatic index of G. If G is bipartite, the cliques in L(G) are exactly the sets of edges in G sharing a common endpoint. Now Kőnig's line coloring theorem, stating that the chromatic index equals the maximum vertex degree in any bipartite graph, can be interpreted as stating that the line graph of a bipartite graph is perfect. Since line graphs of bipartite graphs are perfect, the complements of line graphs of bipartite graphs are also perfect. A clique in the complement of the line graph of G is just a matching in G. And a coloring in the complement of the line graph of G, when G is bipartite, is a partition of the edges of G into subsets of edges sharing a common endpoint; the endpoints shared by each of these subsets form a vertex cover for G. Therefore, Kőnig's theorem itself can also be interpreted as stating that the complements of line graphs of bipartite graphs are perfect. Weighted variants Konig's theorem can be extended to weighted graphs. Egerváry's theorem for edge-weighted graphs Jenő Egerváry (1931) considered graphs in which each edge e has a non-negative integer weight we. The weight vector is denoted by w. The w-weight of a matching is the sum of weights of the edges participating in the matching. A w-vertex-cover is a multiset of vertices ("multiset" means that each vertex may appear several times), in which each edge e is adjacent to at least we vertices. Egerváry's theorem says:In any edge-weighted bipartite graph, the maximum w-weight of a matching equals the smallest number of vertices in a w-vertex-cover.The maximum w-weight of a fractional matching is given by the LP:Maximize w · x Subject to: x ≥ 0E __ AG ·