정점 의 차수를 라고 하자.
라면 답은 이다. 하나를 제거하면 에 연결되어 있던 각 방향이 서로 다른 연결 컴포넌트가 되므로, 정확히 개의 연결 컴포넌트가 남는다.
이제 가 리프라고 하자. 에서 가장 가까운 차수가 이상인 정점을 라고 하고, 와 사이의 거리를 라고 하자.
일 때 제거되는 정점들은 에서 시작하는 하나의 단순 경로를 이룬다. 이 경로의 끝에 도달하기 전까지 차수가 이상인 정점이 없으므로, 남은 그래프는 연결되어 있거나 비어 있다. 따라서 연결 컴포넌트가 개 이상이 될 수 없다.
이면 도 제거된다. 에서 방향으로 향하는 간선을 제외해도 에는 적어도 두 개의 다른 방향이 있다. 이 방향들은 를 제거한 뒤 서로 다른 연결 컴포넌트가 된다. 따라서 리프 의 답은 이다.
차수가 이상인 정점이 트리에 하나도 없다면 트리는 하나의 경로이다. 경로의 리프를 중심으로 어떤 반지름의 정점들을 제거해도 남은 그래프는 하나의 경로이거나 빈 그래프이므로 답은 이다. 인 경우도 같은 이유로 답은 이다.
따라서 다음과 같이 답을 정리할 수 있다.
차수가 이상인 모든 정점을 시작점으로 하는 다중 시작점 BFS를 수행하면, 각 정점에서 가장 가까운 이러한 정점까지의 거리를 한 번에 구할 수 있다.
시간 복잡도는 이고, 메모리 복잡도는 이다.
