Finding the maximum distance from the starting node
The code does not work because of a typo — there is a call to distance_sites but there is no such function.
There are no docstrings. What do these functions do? How do I call them?
In order to improve the performance, we need to measure it, and in order to do that, it's helpful to be able to make test cases of arbitrary sizes. So let's write a test case generator:

from itertools import product

def test_case(n):
    """Construct a graph with n**2 nodes and O(n**2) triangles, and return
    a tuple (graph, capital, number of nodes).

    """
    graph = defaultdict(list)
    for i, j in product(range(n), repeat=2):
        k = i * n + j
        if i &lt; n - 1:
            graph[k].append(k + n)
            graph[k + n].append(k)
        if j &lt; n - 1:
            graph[k].append(k + 1)
            graph[k + 1].append(k)
        if i &lt; n - 1 and j &lt; n - 1:
            graph[k].append(k + n + 1)
            graph[k + n + 1].append(k)
    return graph, 0, n * n


Then we can easily measure the performance of the code using timeit.timeit:

&gt;&gt;&gt; from timeit import timeit
&gt;&gt;&gt; timeit(lambda:distant_sites(*test_case(50)), number=1)
51.7171316598542


with \$n=50\$ the graph has 2,500 nodes and 4,802 triangles.
queue.Queue is a thread-safe data structure intended for use by multi-threaded programs. It has to take and release a lock for every operation, so it is overkill to use this in a single-threaded program. It is more than ten times faster to use collections.deque instead:

&gt;&gt;&gt; timeit(lambda:distant_sites(*test_case(50)), number=1)
4.451224883086979

The code computes the distance from the capital to each town by running a separate breadth-first search for each town. But this repeats a lot of work: in the course of finding the distance to town A, the breadth-first search will have to visit towns B, C, D, and so on. It would make sense to remember the distance to each town as we visit it, and so compute the distances from the capital to all the towns in one go:

from collections import deque

def distances(graph, origin):
    """Return a dictionary mapping each node in graph to its distance from
    the origin.

    """
    result = {origin: 0}
    visited = set([origin])
    queue = deque([origin])
    while queue:
        node = queue.popleft()
        distance = result[node] + 1
        for neighbour in graph[node]:
            if neighbour not in visited:
                result[neighbour] = distance
                visited.add(neighbour)
                queue.append(neighbour)
    return result


This gives a couple of orders of magnitude speedup on the test case:

&gt;&gt;&gt; timeit(lambda:distant_sites(*test_case(50)), number=1)
0.030185375828295946

The code for finding the most distant sites looks at all triangles. But this likely involves a lot of wasted effort. For example, suppose we find a triangle whose nodes have distance 48, 49 and 50 from the origin (with sum 147). Now there is no need to look at any triangle unless it contains a node with distance \${147\over 3} = 49\$ or more. So if we sort the nodes in reverse order by their distance from the origin and just remember the best-scoring site, then we may not have to consider very many sites before we know that we have found the most distant one.

def distant_sites(graph, origin):
    """Return the pair (max_site_dist, site_count), where max_site_dist is
    the maximum distance of any site in the graph from the origin, and
    site_count is the number of sites at that distance. A "site" is a
    triangle of nodes, and its distance from the origin is the sum of
    the distances of the three nodes.

    """
    distance = distances(graph, origin)
    nodes = sorted(((d, n) for n, d in distance.items()), reverse=True)
    max_site_dist = 0
    site_count = 0
    for dist1, node1 in nodes:
        if dist1 * 3 &lt; max_site_dist:
            break
        neighbours = graph[node1]
        for node2 in neighbours:
            dist2 = distance[node2]
            if (dist2, node2) &gt;= (dist1, node1):
                continue
            for node3 in graph[node2]:
                if node3 not in neighbours:
                    continue
                dist3 = distance[node3]
                if (dist3, node3) &gt;= (dist2, node2):
                    continue
                site_dist = dist1 + dist2 + dist3
                if site_dist &gt; max_site_dist:
                    max_site_dist = site_dist
                    site_count = 1
                elif site_dist == max_site_dist:
                    site_count += 1
    return max_site_dist, site_count


The speedup you get from this optimization depends on the kinds of graph you feed it (if there are few sites then it won't make much difference). For my test case we get about 40% speedup:

&gt;&gt;&gt; timeit(lambda:distant_sites(*test_case(50)), number=1)
0.017997111193835735