네 토큰을 줄 세워 1,2,3,4번이라 하고 처음 색은 파랑·빨강·파랑·빨강이에요. 선으로 연결된 두 토큰을 고르면 그 두 색을 동시에 반대로 바꿔요. 연결선이 {1,2},{3,4}뿐일 때 모두 빨강으로 만들 수 있나요? 연결선 {2,3}을 하나 더 허용하면 달라지나요?
처음 파란 토큰은 두 개라 전체 홀짝 검사는 통과해요. 그런데 끊어진 두 묶음에는 각각 파랑이 한 개예요. 묶음 안의 두 색을 함께 바꾸면 그 묶음의 파랑 수는 2만큼 늘거나 줄거나 그대로예요. 각 묶음의 홀짝은 바뀌지 않아요. 모두 빨강인 목표는 두 묶음 모두 파랑0개라 도달할 수 없어요.
가운데 연결선을 허용하면 다음 두 조작으로 목표를 얻어요.
전체 파랑 수의 짝수성만 보는 것과 서로 오갈 수 있는 연결 묶음별로 그 수를 보는 것은 다른 검사예요. 새 선은 색 바꾸기 규칙 자체를 바꾸지 않고 두 묶음을 연결해요.
일반적인 유한 연결 그림에서도 각 연결 묶음의 파랑 수가 짝수이면 모두 빨강으로 만들 수 있어요. 같은 묶음의 파랑 두 점을 잇는 같은 점을 반복해서 지나지 않는 경로 하나를 택해 그 경로의 선을 각각 한 번 조작해요. 양 끝점은 한 번, 중간점은 두 번 바뀌어 끝의 파랑 둘만 빨강이 돼요. 짝들을 반복해서 없애면 돼요. 따라서 묶음별 짝수성이 필요조건이며 충분조건이에요.
전체 파랑 수가 같다는 정보만으로 두 연결 그림의 도달 가능성을 같게 보았는지 확인해 봐요. 실제 대상의 모습보다 어느 쌍에 조작을 허용했는지가 불변량의 단위를 정해요.
착안 원문: Chameleon Island: Two Colors. 원문의 두 색 전환 규칙에서 연결선과 목표 도달 조건을 새로 구성했어요. 원문에 일반 필요충분조건의 증명이 제시되어 있다고 주장하지 않아요.
