Breadth-first tree cutting
For every edge in your graph, you are doing a BFS of the tree on one side of the edge to sum all of its vertex weights. It is not hard to see that you are doing a lot of work over an over again. Imagine that every vertex in your tree was connected to only 2 other vertices, so that it basically looked like a doubly linked list. If we store the list in an array, your code would be doing something akin to:

def min_diff_cut(list_):
    total = sum(list_)
    best_diff = total
    for idx in range(1, len(list_)):
        best_diff = min(best_diff, total - sum(list[:idx]))
    return best_diff


This of course has \$O(n^2)\$ complexity, which is rarely a good thing. A much more efficient implementation running in \$O(n)\$ time would do something like:

def min_diff_cut(list_):
    total = sum(list_)
    best_diff = total
    subtotal = 0
    for value in list_:
        subtotal += value
        best_diff = min(best_diff, total - subtotal)
    return best_diff


How can you expand this idea to work on your possibly branched tree? Well, if instead of breadth first, you go depth first, you can recursively find out what the best diff and sum of weights down an edge is, and come up with a solution from there. This would look something like:

def min_diff_cut(graph, weights):
    total = sum(weights)
    visited = set()

    def subtree_total_weight(vertex):
        visited.add(vertex)
        subdiff = total
        subtotal = weights[vertex]
        for next_vtx in graph[vertex]:
            if next_vtx in visited:
                continue
            subt, subd = subtree_total_weight(next_vtx)
            subtotal += subt
            subdiff = min(subdiff, subd)
        return subtotal, min(subdiff, abs(2*subtotal - total))

    # We are assuming vertices are 0-based indices
    _, best_diff = subtree_total_weight(0)

    return best_diff

if __name__ == '__main__':
    print min_diff_cut({0: [1], 1: [0, 2, 4], 2: [1], 3: [4],
                        4: [1, 3, 5], 5: [4]},
                       [100, 200, 100, 500, 100, 600])