Python's default arguments are evaluated when the function is defined, not when it is called. This means that the default value adj_list=[] in vertex.__init__ is a single list which is reused every time you call vertex(). Thus every vertex ends up with the exact same adjacency list, and you get a complete graph.

Here is a working __init__:

class vertex(object):
    __slots__ = ['color', 'adj_list']
    def __init__(self):
        self.color = None
        self.adj_list = []

where I took out your other member variables, because you don't need them.