Problème coloration de graphe eulérien python

Bonjour,

Nous sommes étudiantes en prépa intégrée d'école d'ingénieur et nous avons un problème python.

Nous devons coder la coloration de graphes eulérien grâce à la méthode de Welsch-Powell qui est la suivante :
1) Repérer le degré de chaque sommet.
2) Ranger les sommets par ordre de degrés décroissants (dans certains cas plusieurs possibilités).
3) Attribuer au premier sommet (A) de la liste une couleur.
4) Suivre la liste en attribuant la même couleur au premier sommet (B) qui ne soit pas adjacent à (A).
5) Suivre (si possible) la liste jusqu'au prochain sommet (C) qui ne soit adjacent ni à A ni à B.
6) Continuer jusqu'à ce que la liste soit finie.
7) Prendre une deuxième couleur pour le premier sommet (D) non encore coloré de la liste.
8) Répéter les opérations 3 à 7.
9) Continuer jusqu'à avoir coloré tous les sommets.

Notre code permet de créer un graphe puis des listes de listes avec le nom du sommet et son degré (c'est à dire le nombre de sommets auxquels il est relié). Nous avons ensuite une matrice d'adjacence qui permet d'obtenir ces degrés. Puis viens le problème de la coloration du graphe, nous n'arrivons pas à obtenir ce que l'on souhaite. Autrement dit, nous n'arrivons pas a colorer le premier sommet avec le plus grand degré ainsi que tout les sommets qui ne sont pas lié à celui-ci de la même couleur.

Finalement notre problème vient au moment de la coloration, cela ne colore pas correctement.

Pouvez vous nous aider ? Merci d'avance :)

import numpy as np

#permet de créer les arrêtes grâce au sommet initial et au sommet final
class Arete:
    #permet d'initialliser les paramètre de la class
    def __init__(self, initial=0, final=0):
        self.sommet_initial=initial # sommet initial de l'arête
        self.sommet_final=final # sommet final de l'arête
        
    #demnde à l'utilisateur d'entrer le sommet initial et le sommet final pour chaque
    def saisie_arete (self):
        self.sommet_initial=int(input("sommet initial? "))
        self.sommet_final=int(input("sommet final? "))
        return self
        
#permet de créer tout le graphe en interne (grâce au nombre de sommets et aux arrêtes)  
class Graphe:
    #initialisation des données de la class
    def __init__(self, ns=0, na=0, aretes=[]):
        self.nombre_sommet=ns # nombre de sommets du graphe
        self.nombre_arete=na #nombre d'aretes du graphe
        self.liste_aretes=aretes # liste des arêtes du graphe
        
    #demande à l'utilisateur les données dont nous avons besoin pour créer le graphe
    #demande le nombre de sommet puis le nombre d'arrêtes (car peuvent être différents)
    def saisie_graphe(self):
        self.nombre_sommet=int(input("combien de sommet dans le graphe? "))
        self.nombre_arete=int(input("combien d'aretes dans le graphe? "))
    #cela permet d'appeler la fonction de saisie des arrêtes présente dans la class Arete
    #reitére n fois l'opération n etant le nombre d'arrête que l'utilisateur à renseigné plus tôt
        for i in range (0,self.nombre_arete):
            self.liste_aretes.append(Arete.saisie_arete(Arete(0,0)))
        return self
    
    #créer la matrice d'adjacence qui nous renseigne sur le degré de chaque sommet
    def matrice(self):
        sommets=[]#on ne prends chaque sommets qu'une seule fois
        deg=[] #liste de liste des sommets et degré non trié
        #permet de mettre dans la liste tout les chifffres entrées
        for i in self.liste_aretes:
            sommets.append(i.sommet_initial)
            sommets.append(i.sommet_final)
        lsommets=sommets[:]
        
        #permet de compter le nombre de fois que le sommet
        #apparait et le garder qu'une seule fois
        for a in sommets:
            while sommets.count(a)>1:
                sommets.remove(a)
        for a in sommets:#fois 2 sinon ça ne marche pas
            while sommets.count(a)>1:
                sommets.remove(a)
        sommets.sort() #permet de trier les sommets par ordre croissant (de noms)
        print(sommets)
        
        #si l'utilisateur se trompe et rentre des informations impossible donc incorrecte
        #cela renvoie une erreur
        if self.nombre_sommet < len(sommets):
            print("le nombre de sommet prévu et le nombre de sommet rentré n'est pas le meme")
        else:
            #enregistre le degré de chaque sommet dans une liste de liste
            for o in sommets :
                d=lsommets.count(o) #degré d'un sommet
                s=[o,d] #liste avec nom et degré
                deg.append(s) #implémente le degré de chaque sommet dans la liste vide deg
            # permet de trier par ordre décroissant les sommets suivant leur degrés
            degtri=sorted(deg, key=lambda x:x[1], reverse=True)
            print (sorted(deg, key=lambda x:x[1], reverse=True))
            
            #création de la matrice d'adjacence
            mat=np.zeros((self.nombre_sommet,self.nombre_sommet))
            
            
            #implémente les informations dans la matrice et l'affiche
            for i in self.liste_aretes:    
                coord1=sommets.index(i.sommet_initial)
                coord2=sommets.index(i.sommet_final)
                mat[coord1,coord2]=1
                mat[coord2,coord1]=1
            print (mat)
            
            #CEST LA QUE CA BEUUUG
            d=1
            
            #création d'une liste vide pour pouvoir mettre les noms des sommets
            for z in range(self.nombre_sommet):
                co=[]
                w=degtri[z][0]-1
                e=degtri[z][1]
                if e>0:
                    for p in range (1,self.nombre_sommet):
                        if mat[p-1  ,w]==0:
                            co.append(degtri[p-1][0])
                            degtri[p-1][1]=0
                            degtri[z][0]=0
                            
                
                    with open("couleur.txt",'r') as fich:
                        for i in range(d):
                            ligne = fich.readline()
                    print(co, "est de la couleur", ligne)
                d=d+1
                
                #print(z)
            


print(Graphe.matrice(Graphe.saisie_graphe(Graphe(0,0,[]))))