Prove or disprove: K9 decomposes into copies of C9.

K9의 엣지 개수는 9*(8/2)=36개이고, C9의 엣지개수는 9개이니, 36/9=4로 나누어 떨어져 이론적으로는 4개의 C9 copy로 분해되는게 가능함. 주의할건 이걸로 증명을 마쳐선 안됨. 그 존재성까지 증명해야 증명이 마무리되며, 이는 실제로 보여줌으로써 해결할 수 있음.

 

본인은 시계방향으로 9개 정점을 0부터 8까지 라벨링하고, 4개의 다른 경로를 가진 C9을 구성함으로써 증명을 해결하였음. 예를 들어,

0-1-2-3-4-5-6-7-8-0 으로 1개 발견, 0-2-4-6-8-1-3-5-7-0으로 2개 발견,...이렇게 4개를 찾아보길 바람.