딕 반 다이크 쇼라는 TV 프로그램에서, 딕의 아들 리치가 등에 있는 주근깨들을 연결하는 선을 그어서 자유의 종을 그리는 에피소드가 나온 적이 있다.

딕의 등을 여러 (x, y) 위치에 주근깨가 있는 평면이라고 생각해보자. 지금 우리는 리치가 최소한의 잉크로 점을 연결할 수 있는 방법을 알려줘야 한다. 리치는 점 사이에 직선을 긋는 식으로 점을 연결한다. 그리고 각 직선을 그을 때마다 펜을 등에서 뗀다. 이 일이 끝나고 나면 등에 있는 모든 주근깨가 연결되어야 한다.

참고사항
1. 각 점(노드)이 모두 연결된 그래프에서 최소신장트리를 구하는 문제.
2. 프림 알고리즘 / 크루스칼 알고리즘

평면 위에 지도가 있을 때, 각 영역을 인접한 다른 영역과 구분할 수 있게 서로 다른 색으로 칠하고자 한다면, 네 가지 색만 있으면 된다는 4색 정리라는 것이 있다. 이 정리는 100년이 넘게 증명되지 않은 채로 남아 있다가 1976년에 컴퓨터의 도움을 받아서 증명될 수 있었다. 여기에서는 조금 더 쉬운 문제를 풀면 된다. 어떤 연결 그래프가 주어졌을 때 그 그래프를 두 색으로 칠할 수 있는지, 즉 모든 정점을 빨간색 또는 검은색으로 칠할 때 인접한 정점이 같은 색으로 칠해지지 않게 할 수 있는지 알아보자. 문제를 간단하게 하기 위해 그래프가 연결 그래프고, 무방향 그래프며, 자체 루프가 없다고(즉 (x,x)같이 한 정점에서 출발해서 그 정점으로 바로 연결되는 모서리가 없다고) 가정하자.