from copy import copy

def eh_conexo(grafo):     
    v_0=list(grafo)[0] # comece pelo primeiro vertice do grafo.
    cor_vertice = {v: 'vermelho' for v in grafo} 
    cor_vertice[v_0]='azul'
    V=[v_0]
    while len(V)!=0:
        u=V.pop()
        for v in grafo[u]:
            if  cor_vertice[v]=='vermelho':
                cor_vertice[v]='azul'
                V.append(v)
            
            cor_vertice[u]='preto'
    return list(cor_vertice.values()).count('preto')==len(grafo)


   

def lista_vertice_grau_impar(grafo):
    lista_vertice_grau_impar= []   #inicia lista vazia
    for k in grafo:            
       if len(grafo[k]) % 2 != 0:   
            lista_vertice_grau_impar.append(k)
    return lista_vertice_grau_impar            

def par_de_ligados(grafo):
    par_de_ligados = []
    for u in grafo:
        for v in grafo[u]:
            par_de_ligados.append((u,v))
    return par_de_ligados
    
#Algorithm de Fleury's
     
def fleury(grafo):
    
    if len(lista_vertice_grau_impar(grafo))>2 or len(lista_vertice_grau_impar(grafo))==1:
            return 'nao eh eureliano'
    else:
            g=copy(grafo)                 
            caminho=[]
            if len(lista_vertice_grau_impar(g))==2:
                        v=lista_vertice_grau_impar(g)[0]
   
            else:
                v = list(g)[0]
            while len(par_de_ligados(g)) > 0:
                vertice_atual = v
                for v in g[vertice_atual]:
                    g[vertice_atual].remove(v)
                    g[v].remove(vertice_atual)
                    ponte = not eh_conexo(g)
                    if ponte:
                        g[vertice_atual].append(v)
                        g[v].append(vertice_atual)
                    else:
                        break
                if ponte:
                    g[vertice_atual].remove(v)
                    g[v].remove(vertice_atual)
                    g.pop(vertice_atual)
                caminho.append((vertice_atual, v))
    return caminho
G = {1:[2, 5],  2: [1, 3, 5],  3: [2, 4],  4: [3, 5, 6],  5: [1, 2, 4],  6: [4]}
G1 = {1: [2, 3, 4, 4], 2: [1, 3, 3, 4], 3: [1, 2, 2, 4], 4: [1, 1, 2, 3]}
print fleury(G1)

[(1, 2), (2, 3), (3, 1), (1, 4), (4, 3), (3, 2), (2, 4), (4, 1)]