Теория графов(дискретная математика)

1. Show that a 2-edge-connected graph G has list chromatic number equal to two if and only if either G is an even cycle or G can be obtained from K 2,3 by subdividing one of its edges even number of times, i.e., G consists of two vertices joined by an even path and two two-edge paths.

2. Show that the decision problem whether the vertices of an input multigraph G, i.e., a graph with parallel edges, can be partitioned into sets A and B such that there are at least k edges between A and B (k is part of input) is NP-complete.

3. Show that for every integer k, the decision problem whether the vertices of an input graph G can be partitioned into sets A and B such that there are at least k edges between A and B can be solved in polynomial time.