삼차 그래프
큐빅 그래프(cubic graph)는 모든 꼭지점이 정확히 세 개의 변에 접한 그래프를 의미한다. 즉, 큐빅 그래프는 3-정규 그래프이다.
1880년에 피터 거스리 테이트는 모든 큐빅 그래프는 해밀톤 경로를 가진다는 추측을 내놓았지만, 1946년에 Tutte이 46개 꼭지점을 가진 반례를 찾았다.
1971년에 Tutte은 모든 이분 큐빅 그래프는 해밀톤 회로가 있을 것이라고 추측했지만, Horton이 96개 꼭지점을 가진 반례를 찾아냈다.
2003년에 Petr Hliněný가 큐빅 그래프의 최소 교차점 개수를 찾는 문제는 NP-난해임을 증명하였다.