추천문제

너무 할게 없어서 Lovasz 다시 붙잡고 몇문제 풀어봤는데 괜찮은 문제가 있어서 공유 차원에 올린다. 사실 풀이까지 쓰려했는데 솔직히 쓰려니 너무 많네...

나는 푸는데 한참 걸렸다.

Lemma. Suppose that G is 2-connected. Let T_1, T_2 be two spanning trees of a connected graph G. Then to obtain T_1 from T_2 it suffices repeatedly to apply the following transformation: we remove the edge adjacent to some endpoint x of the tree and connect x to the rest by some other edge of G.

Problem.

(a) Let G be a 2-connected graph on n points and n_1+n_2=n. Then V(G) has a partition {A_1,A_2} such that #A_i=n_i and each A_i induces connected subgraph.

(b) Let G be a 2-connected non-bipartite graph on 2m points. Then V(G) has a partition {A_1,A_2} such that #A_i=m and (A_1,A_2) edges form a connected spanning subgraph.

개인적으로 이 중에서 problem (a)가 가장 무난하다. 힌트로는 lemma 풀 땐 backward induction, problem (b)를 풀 땐 non-bipartite의 동치조건을 먼저 생각하길... 그리고 lemma에서 최대한 많은 것을 얻어내야 한다. 저 lemma의 statement 자체만 쓰이는 것이 아니다.

(A. Bondy,-L. Lovasz)