List passing by "reference" even though list() constructor used in Python

Question

I am trying to implement Karger's algorithm and am having trouble with lists in Python.

I have an input list input_v that should stay static throughout the program. Inside a while loop, I do max_iters iterations of Karger's algorithm with a list copy of input_v called vertices. At the end of 1 iteration of the inside for loop, it seems that all the logic I applied on vertices was also applied on input_v, even though I did vertices = list(input_v).

input_v = [[[1], 2, 3, 4], [[2], 1, 4], [[3], 1, 4], [[4], 2, 3]]

# Perform Karger's n^2ln(n) times to ensure p > 1-1/n
for i in range(0, max_iters):

    vertices = list(input_v)
    print 'new loop'
    print vertices
    print input_v

    #Contract edges n-2 times to find A and B
    for j in range(0, n - 2):

        # length of current array
        len_arr = n - j

        #rand_vn => random index within current array
        #i_vn => true index of vertex from orig array

        # Randomly select 1st vertex (v1) to contract
        rand_v1 = randint(1, len_arr) - 1
        i_v1 = vertices[rand_v1][0][0]

        # Randomly select 2nd vertex (v2) connected to v1
        i_in_v1 = randint(1,len(vertices[rand_v1]) - 1)
        i_v2 = vertices[rand_v1][i_in_v1]

        for k in range(0, len_arr):
            if i_v2 in vertices[k][0]:
                rand_v2 = k

        for y in vertices[rand_v2][1:]:
            if y not in vertices[rand_v1]:
                vertices[rand_v1].append(y);

        # Remove each other's indices from list of edges
        for q in vertices[rand_v2][0]:
            if q in vertices[rand_v1]:
                vertices[rand_v1].remove(q)
            # Add indices from v2 to v1 (supernode)
            vertices[rand_v1][0].append(q)

        for r in vertices[rand_v1][0]:
            if r in vertices[rand_v1]:
                vertices[rand_v1].remove(r)

        vertices.pop(rand_v2)

        print vertices

    del vertices[:]

And here's the output after shortly beginning the 2nd iteration.

new loop
[[[1], 2, 3, 4], [[2], 1, 4], [[3], 1, 4], [[4], 2, 3]] # input_v 
[[[1], 2, 3, 4], [[2], 1, 4], [[3], 1, 4], [[4], 2, 3]] # vertices
[[[1, 3], 2, 4], [[2], 1, 4], [[4], 2, 3]]
[[[1, 3, 2], 4], [[4], 2, 3]] # vertices at the end of Karger's
new loop
[[[1, 3, 2], 4], [[2], 1, 4], [[3], 1, 4], [[4], 2, 3]] # input_v (seems to be a hybrid)
[[[1, 3, 2], 4], [[2], 1, 4], [[3], 1, 4], [[4], 2, 3]] # vertices
[[[1, 3, 2], 4], [[2], 1, 4], [[3, 4], 1, 2]]
[[[1, 3, 2, 3, 4]], [[2], 1, 4]] # Garbage because of unexpected behaviour