Problème du second voisinage

Je pense avoir trouvé un contre-exemple, mais j'arrive pas à le poster ?

Excuse @serge, je pense que j'avais fait une erreur dans la saisie. Le graphe ne marche pas en tant que contre-exemple. Je crois maintenant que la conjecture est vraie.
Je pense savoir montrer que tout graphe orienté simple contenant un cycle contient un sommet solution. Il suffit alors de savoir prouver que tout graphe dont tout sommet est de degré minimal 1, contient un cycle.
Merci.

Je n'arrive toujours pas à vérifier mon contre-exemple qui est un graphe à 55 sommets. Je pense que ton programme est un peu trop lourd pour des graphes d'une cinquantaine de sommets...
Je voudrais connaitre par ailleurs le code LATEX pour dessiner ''un arc'' (arête orienté), comme ça, je pourrais envoyer le graphe schématisé que j'ai construit. Merci d'avance.

Merci AD pour la remarque.
Zut ! j'ai vu que j'ai mal compté encore une fois.

Pardon, j'ai oublié le fichier dans le message précédent. Il s'agit d'un graphe d'ordre 100.

Merci @AD.
Désolé, il y a encore une erreur : le graphe comporte les arêtes $[a, g]$ et $[g, a]$.
J'invite à chercher un contre-exemple (c'est amusant), mais je commence à me sentir un peu seul.
Bienvenue...

Tiens je te file un code pour vérifier si tes graphes contiennent des cycles de longueur 2 comme ça tu pourras faire joujou longtemps avant de revenir...

Sur cette page tu insères le code suivant dans la partie gauche : 

import numpy as np

T=[[1,10],[1,11],[1,12],[1,13]] #insérer tous les sommets ici entre les crochets

A=np.zeros((np.amax(T),np.amax(T)), dtype=int)

for c in T:
    A[c[0]-1,c[1]-1]=1

def is_valid(A):
    d = A.shape
    if d[0]!= d[1]:
        print("Erreur : la matrice d'adjacence n'est pas carrée")
        return

    for i in range(d[0]):
        for j in range(d[1]):
            if A[i,j] == 1 and A[j,i] ==1:
                print(f"Erreur : cycle de longueur 2 trouvé {(i+1,j+1)} et {(j+1,i+1)}")
                return
    print("C'est valide")

is_valid(A)

puis tu exécutes les étapes suivantes : 

1) cliquer sur "Run"
2) lire le message d'erreur indiquant le cycle de longueur 2 présent dans le graphe (tu en auras toujours un ne t'en fait pas... 🤣)
3) corriger le graphe
4) revenir au point 1)

Salut.
Après avoir tenté en vain de trouver un contre-exemple à la conjecture, je suis revenu à essayer de prouver sa véracité.
Ma méthode est de montrer que s'il existait un graphe $G$ d'ordre $n\in\,\mathbb{N}^*$, ne vérifiant pas la conjecture (c'est-à-dire tel que $\forall s\in G,\,G_{1}(s)\gt G_{2}(s)$, où $G_{1}(s)$ désigne le nombre de voisins de $s$ et $G_{2}(s)$ le nombre de second voisins de $s$ dans $G$), alors il existe un graphe $G'$, sous graphe de $G$, d'ordre $n - 1$ ne vérifiant pas la conjecture. Pour cela, on raisonne comme suit.

Supposons qu'il existe un graphe $G$ d'ordre $n\in\,\mathbb{N}^*$ avec $n\gt 6$, tel que $\forall s\in G,\,G_{1}(s)\gt G_{2}(s)$.
Soit $x_{1}\in\,G$, on a que $\forall x$ précédent de $x_{1}$ (c'est-à-dire que $x_{1}$ est voisin de $x$), $x_{1}$ a un voisin qui n'est pas voisin de $x$, et alors si on enlève le sommet $x_{1}$ de $G$, on obtient un graphe $G'$ d'ordre $n - 1$, sous graphe de $G$ tel que $\forall s\in G',\,G'_{1}(s)\gt G'_{2}(s)$. C'est dire qu'on a alors un graphe $G'$ d'ordre $n - 1$ ne vérifiant pas la conjecture.
Sinon $\exists\, x_{2}$ précédent de $x_{1}$ tel que tous les voisins de $x_{1}$, sont des voisins de $x_{2}$. Tenons alors le raisonnement précédent sur $x_{2}$, à savoir :
$\forall x$ précédent de $x_{2}$, $x_{2}$ a un voisin qui n'est pas voisin de $x$, et alors si on enlève le sommet $x_{2}$ de $G$, on obtient un graphe $G'$ d'ordre $n - 1$, sous graphe de $G$ tel que $\forall s\in G',\,G'_{1}(s)\gt G'_{2}(s)$. C'est dire qu'on a alors un graphe $G'$ d'ordre $n - 1$ ne vérifiant pas la conjecture.
Sinon $\exists\, x_{3}$ précédent de $x_{2}$ tel que tous les voisins de $x_{2}$, sont des voisins de $x_{3}$ (Retenons que $x_{1}$ et tous ses voisins sont alors voisins de $x_{3}$).
Ce processus s'arrête à un certain $x_{i},\, (1\lt i\lt n)$, alors il existe $G'$ sous graphe de $G$ d'ordre $n - 1$, tel que $\forall s\in G',\,G'_{1}(s)\gt G'_{2}(s)$. C'est dire qu'on a alors un graphe $G'$ d'ordre $n - 1$ ne vérifiant pas la conjecture.
Sinon $\exists\, x_{n}\in\,G$ tel que tous les sommets de $G$ sont des voisins de $x_{n}$. Mais alors, si on enlève $x_{n}$, chacun des sommets $s$ de $G$ restants sera tel que $G'_{1}(s)\gt G'_{2}(s)$, car $x_{n}$ n'était ni voisin, ni second voisin d'aucun de ces sommets restants de $G$.

On a donc montrer que s'il existait un graphe qui ne vérifie pas la conjecture, il existerait toujours un graphe plus petit qui ne vérifie pas la conjecture. De proche en proche, il existerait alors un graphe d'ordre inférieur à $6$ qui ne vérifierait pas la conjecture ;.ce qui est absurde, parce qu'il a été démontré, qu'un contre-exemple à la conjecture serait d'ordre supérieur à $6$.
Cqfd.

Un petit coup d'épingle dans une démonstration gonflable et l'homme qui y jouit, en général, devient triste. Mais toi, tu n'es jamais triste: Tu la rustines et c'est reparti. Je t'économise une rustine.