모두 직접 연결된다
A,B,C가 서로 세 간선으로 연결되어 있으면 {A,B,C}는 클리크다. A와 C가 B를 거쳐 갈 수만 있고 직접 연결되어 있지 않다면 세 정점 전체는 클리크가 아니다.
그래프 전체일 필요는 없다
큰 그래프 안의 일부 정점만 선택해도 클리크가 될 수 있다. 선택하지 않은 정점들과 어떤 연결이 있는지는 그 선택 집합의 클리크 여부를 직접 바꾸지 않는다.
극대와 최대
극대 클리크는 정점을 더 넣어 클리크를 키울 수 없는 경우다. 최대 클리크는 그래프 전체에서 원소 수가 가장 큰 클리크다. 더 늘릴 수 없다는 조건만으로 가장 크다는 결론은 나오지 않는다.
색칠의 하한
크기가 k인 클리크에서는 모든 정점 쌍이 인접하므로 적어도 k개의 서로 다른 색이 필요하다. 따라서 그래프의 채색수는 그 안의 어떤 클리크 크기보다도 작을 수 없다.
관련 문서
독립 집합 (그래프 이론) / 완전 그래프 / 채색수 / 그래프 색칠 / 정점 (그래프 이론) / 간선 (그래프 이론) / 부분집합