그래프 G = (V, W)를 유한개의 정점의 집합 V = {P_1, ... P_n}과 이것들을 잇는 변의 집합 W = {E_1, .... E_n}이 만드는 도형으로 한다. 각 변 E_j는 정확히 두개의 정점 P_i1, P_i2 ( i_1 ≠ i_2 )를 가진다. 정점 이외의 변끼리의 교점은 생각하지 않는다. 그리고, 각 정점엔 백이나 흑으로 색이 칠해져있다고 정의한다.


예를 들어, 그림 (1)의 그래프는 정점이 n = 5개, 변이 m = 4개 있으며, 변 E_i(i = 1, ..., , 4)의 정점은 P_i와 P_5이다. P_1, P_2는 흰 정점, P_3, P_4, P_5는 검은 정점이다.


출발점으로 하는 그래프는 그림(2)로, n = 1, m = 0이며, 단 한개의 정점은 흰 정점으로 한다.


주어진 그래프 G = (V, W)로부터 새로운 그래프 G' = (V', W')을 만드는 두 종류의 작업을 이하에서 정의한다. 이 작업들로는 정점과 변의 수를 각각 1개씩밖에 늘리지 못한다.

a76a08ad230e692cb9675d73ca836a2db379dda33416fb20fbf7991cdb1


작업 (1)

이 작업은 G의 정점 P_i0를 고르면 정해진다. V'는 V에 P_n+1을 더한 것으로, W'는 W에 E_m+1을 더한 것으로 한다. E_m+1의 정점은 P_i0과 P_n+1으로 하며, G에 있어서 P_i0의 색이 백 또는 흑일때, G'에 있어서의 P_i0의 색은 각각 흑 또는 백으로 변화한다. 그 이외의 정점의 색은 변화하지 않는다. 또한 P_n+1은 흰 정점으로 한다.

a76a08ad230e6be87eb1d19528d5270379b1b345b78f2


작업 (2)

이 작업은 G의 변 E_j0을 하나 고르면 정해진다. V'는 V에 P_n+1을 더한 것으로 한다. W'는 W에서 E_j0을 제거하여, 새로운 변 E_m+1, E_m+2를 더한 것으로 한다. E_j0의 정점이 P_i1과 Pi2일 때, E_m+1의 정점은 P_i1과 P_n+1이며, E_m+2의 정점은 P_i2과 P_n+1인 것으로 한다. G'의 그 이외의 변의 정점은 G에서의 대응하는 변의 정점과 같은 것으로 한다. G에 있어서 P_i1의 색이 백 또는 흑일때, G'에 있어서의 P_i1의 색은 각각 흑 또는 백으로 변화한다. G에 있어서 P_i0의 색이 백 또는 흑일때, G'에 있어서의 P_i0의 색은 각각 흑 또는 백으로 변화한다. 그 이외의 정점의 색은 변화하지 않는다. 또한 P_n+1은 흰 정점으로 한다.


a76a08ad230e6ce87eb1d19528d52703a183e373c4163


출발점의 그래프 G_1에 이 두가지 작업을 반복하여주는것으로 얻을 수 있는 그래프를 가능그래프라 부르는 것으로 한다.


문제


(1) 그림 (5)의 세 그래프가 가능그래프인 것을 보이시오. 단 모든 정점은 흰 정점으로 한다.


(2) n을 자연수라 하였을때, n개의 정점을 가지는 그림 (6)과 같은 봉 모양의 그래프가 가능그래프가 되기 위해 n이 만족해야하는 필요충분조건을 구하시오. 단 모든 정점은 흰 정점으로 한다.

a76a08ad230e6de87eb1d19528d52703412848330287