def search(graph, node, maxdepth = 10, depth = 0):
    nodes = []
    for neighbor in graph.neighbors_iter(node):
        if graph.node[neighbor].get('station', False):
            return neighbor
        nodes.append(neighbor)

Why store the neighbor in the list? Instead of putting it in a list, just combine your two loops.

for i in nodes:

i typically stands for index. I suggest using neighbor to make your code easier to follow

    if depth+1 > maxdepth:
        return False

This doesn't relate to this individual node, what is it doing inside this loop.

        if search(graph, i, maxdepth, depth+1):
            return i
   return False

Failure to find is better repoted using None than False.

def search(graph, node, maxdepth = 10, depth = 0):
    nodes = []
    for neighbor in graph.neighbors_iter(node):
        if graph.node[neighbor].get('station', False):
            return neighbor
        nodes.append(neighbor)

Why store the neighbor in the list? Instead of putting it in a list, just combine your two loops.

for i in nodes:

i typically stands for index. I suggest using neighbor to make your code easier to follow

    if depth+1 > maxdepth:
        return False

This doesn't relate to this individual node. What is it doing inside this loop?

        if search(graph, i, maxdepth, depth+1):
            return i
   return False

Failure to find is better reported using None rather than False.