Problème du second voisinage

Salut.
Après avoir en vain chercher un contre-exemple, je fais un retour au bercail en regardant à nouveau ma preuve par récurrence de la conjecture.
On sait que si un graphe contient un sommet de degré nul, il contient alors un sommet solution, en l'occurrence, ce sommet de degré nul.

On considère alors dans la suite que des graphes dont tous les sommets sont de degré supérieur à 0.

Soit la propriété $P_{i}$ :'' tout graphe $G$ d'ordre $i$ admet un sommet $s$ solution (au sens que $G_{1}(s)\leq G_{2}(s)$)''.
Il est évident que $P_{3}$ est vraie.
Supposons $P_{i}$ vraie pour $i$ allant de $1$ à $n - 1$ et montrons que $P_{n}$ vraie.
Soit un graphe $G$ d'ordre $n$. On le partitionne en sous-ensembles $E_{i})_{1\leq i\leq k}$ (où $k$ est un entier naturel non nul, certes $\leq n$) composé chacun par les sommets de $G$ qui ont les mêmes voisins en dehors d'eux-mêmes. On note $F_{i}$ l'ensemble de ces voisins en dehors de $E_{i}$ des sommets de $E_{i}$. k est fini, donc l'ensemble des $F_{i}$ à un élément de cardinal minimal $F_{i_{0}}, i_{0}\in [\![1, k]\!]$. Il existe alors un sommet $s$ de $E_{i_{0}}$ qui est solution.
En effet d'après notre hypothèse, il existe au moins un sommet $s$ de $E_{i_{0}}$ qui est solution dans le sous-graphe $E_{i_{0}}$ de $G$, car ce sous-graphe est d'ordre inférieur à $n$.
Mais par ailleurs un élément de $F_{i_{0}}$ appartient à un ensemble $E_{i}, i\in [\![1, k]\!]$ et on a donc $|F_{i_{0}}\leq |F_{i}|$ (où |.| désigne le cardinal). C'est dire que l'ensemble des voisins de $s$ qui sont dans $E_{i_{0}}$ est $\leq$ à l'ensemble des second voisins de $s$ qui sont dans $E_{i_{0}}$ et que l'ensemble des voisins de $s$ qui sont dans $F_{i_{0}}$ est $\leq$ à l'ensemble des second voisins de $s$ issus de ces derniers. En notant que les voisins de $s$ qui sont dans $F_{i_{0}}$ ne peuvent pas avoir des voisins dans $E_{i_{0}}$, on en déduit que le nombre de voisins de $s$ dans $G$ est $\leq$ au nombre de second voisins de $s$ dans $G$. C'est dire que $s$ est solution au sens que $G_{1}(s)\leq G_{2}(s)$.
On a montré que $P_{3}$ est vraie et si $P_{3}, P_{4}, \cdots, P_{n-1}$ sont vraies alors $P_{n}$ est vraie. Donc quel que soit $n\geq 3$ $P_{n}$ est vraie.
Alors la conjecture est vraie.
Cqfd.

Cordialement.

PS 1 : je pense qu'il reste à clarifier dans la démonstration. A bientôt, si ce n'est que ça.
PS 2 : le raisonnement est encore faux, parce que $F_{i_{0}}$ n'a que des éléments d'un unique $E_{i}$.
Désolé !
PS 3 : je pense qu'en fait, on peut s'en sortir, mais les $E_{i}$ ne doivent pas former une partition, mais plutôt un recouvrement de l'ensemble des sommets du graphe. A bientôt.

@serge pour ton idée de preuve avec des cycle, je pense que les sommets pivots que tu obtiens ont bien sur chacun un seul voisin dans le cycle, mais pas nécessairement dans le graphe complet. Et donc ta dernière égalité est fausse en général.

Ben j'ai essayé de la récrire plus rigoureusement, mais je me rends compte que l'assertion suivante

babsgueye a écrit:

Mais alors si on enlève $s_{j-1}$, on obtient un graphe d'ordre $n$ qui ne contient pas de sommet solution.

est fausse.
En fait je pensais qu'en enlevant $s_{j-1}$, $s_{j}$ ne va pas être sommet solution parce qu'il perd un voisin et un second voisin. Mais en fait, il peut ne pas perdre le second voisin, parce qu'ils peuvent être liés par un autre chemin.

Par ailleurs je pense avoir décrit les agrégats nécessaires pour avoir un contre-exemple. Le problème reste de savoir s'il est possible d'avoir un graphe avec un sommet $s$ qui vérifie toutes les contraintes décrites dans le texte....
Je continue de chercher.

Ok d'accord pour l'exemple.
Sinon pour ta méthode, je pense que tu peux te concentrer sur le point b). C'est le plus important.
Moi j'ai pas encore abandonné la recherche d'un contre-exemple

Salut.
Je propose encore ici un contre-exemple et j'espère que c'est le bon. C'est un graphe d'ordre $45$ dont les sommets notés de $1$ à $45$ sont liés par les arcs suivants. J'espère ne pas avoir fait d'erreur de saisi.

[1,13],[1,14],[1,15],[1,10],[1,11],[1,12],[1,16],[1,17],[1,18],[1,19],[1,20],[1,21],[1,22],[1,23],[1,24],[1,25],[1,26],[1,27]
[1,28],[1,29]
[2,13],[2,14],[2,15],[2,10],[2,11],[2,12],[2,16],[2,17],[2,18],[2,19],[2,20],[2,21],[2,22],[2,23],[2,24],[2,25],[2,26],[2,27]
[2,28],[2,29]
[3,13],[3,14],[3,15],[3,10],[3,11],[3,12],[3,16],[3,17],[3,18],[3,19],[3,20],[3,21],[3,22],[3,23],[3,24],[3,25],[3,26],[3,27]
[3,28],[3,29]
[4,1],[4,2],[4,3],[4,13],[4,14],[4,15],[4,16],[4,17],[4,18],[4,19],[4,20],[4,21],[4,22],[4,23],[4,24],[4,25],[4,26],[4,27]
[4,28],[4,29]
[5,1],[5,2],[5,3],[5,13],[5,14],[5,15],[5,16],[5,17],[5,18],[5,19],[5,20],[5,21],[5,22],[5,23],[5,24],[5,25],[5,26],[5,27]
[5,28],[5,29]
[6,1],[6,2],[6,3],[6,13],[6,14],[6,15],[6,16],[6,17],[6,18],[6,19],[6,20],[6,21],[6,22],[6,23],[6,24],[6,25],[6,26],[6,27]
[6,28],[6,29]
[7,4],[7,5],[7,6],[7,1],[7,2],[7,3],[7,16],[7,17],[7,18],[7,19],[7,20],[7,21],[7,22],[7,23],[7,24],[7,25],[7,26],[7,27]
[7,28],[7,29]
[8,4],[8,5],[8,6],[8,1],[8,2],[8,3],[8,16],[8,17],[8,18],[8,19],[8,20],[8,21],[8,22],[8,23],[8,24],[8,25],[8,26],[8,27]
[8,28],[8,29]
[9,4],[9,5],[9,6],[9,1],[9,2],[9,3],[9,16],[9,17],[9,18],[9,19],[9,20],[9,21],[9,22],[9,23],[9,24],[9,25],[9,26],[9,27]
[9,28],[9,29]
[10,7],[10,8],[10,9],[10,4],[10,5],[10,6],[10,16],[10,17],[10,18],[10,19],[10,20],[10,21],[10,22],[10,23],[10,24],[10,25],[10,26],[10,27]
[10,28],[10,29]
[11,7],[11,8],[11,9],[11,4],[11,5],[11,6],[11,16],[11,17],[11,18],[11,19],[11,20],[11,21],[11,22],[11,23],[11,24],[11,25],[11,26],[11,27]
[11,28],[11,29]
[12,7],[12,8],[12,9],[12,4],[12,5],[12,6],[12,16],[12,17],[12,18],[12,19],[12,20],[12,21],[12,22],[12,23],[12,24],[12,25],[12,26],[12,27]
[12,28],[12,29]
[13,10],[13,11],[13,12],[13,7],[13,8],[13,9],[13,16],[13,17],[13,18],[13,19],[13,20],[13,21],[13,22],[13,23],[13,24],[13,25],[13,26],[13,27]
[13,28],[13,29]
[14,10],[14,11],[14,12],[14,7],[14,8],[14,9],[14,16],[14,17],[14,18],[14,19],[14,20],[14,21],[14,22],[14,23],[14,24],[14,25],[14,26],[14,27]
[14,28],[14,29]
[15,10],[15,11],[15,12],[15,7],[15,8],[15,9],[15,16],[15,17],[15,18],[15,19],[15,20],[15,21],[15,22],[15,23],[15,24],[15,25],[15,26],[15,27]
[15,28],[15,29]

[16,30],[16,31],[16,32],[16,33],[16,34],[16,35],[16,36],[16,37],[16,38],[16,39],[16,40],[16,41],[16,42],[16,43],[16,44],[16,45]
[17,30],[17,31],[17,32],[17,33],[17,34],[17,35],[17,36],[17,37],[17,38],[17,39],[17,40],[17,41],[17,42],[17,43],[17,44],[17,45]
[18,30],[18,31],[18,32],[18,33],[18,34],[18,35],[18,36],[18,37],[18,38],[18,39],[18,40],[18,41],[18,42],[18,43],[18,44],[18,45]
[19,30],[19,31],[19,32],[19,33],[19,34],[19,35],[19,36],[19,37],[19,38],[19,39],[19,40],[19,41],[19,42],[19,43],[19,44],[19,45]
[20,30],[20,31],[20,32],[20,33],[20,34],[20,35],[20,36],[20,37],[20,38],[20,39],[20,40],[20,41],[20,42],[20,43],[20,44],[20,45]
[21,30],[21,31],[21,32],[21,33],[21,34],[21,35],[21,36],[21,37],[21,38],[21,39],[21,40],[21,41],[21,42],[21,43],[21,44],[21,45]
[22,30],[22,31],[22,32],[22,33],[22,34],[22,35],[22,36],[22,37],[22,38],[22,39],[22,40],[22,41],[22,42],[22,43],[22,44],[22,45]
[23,30],[23,31],[23,32],[23,33],[23,34],[23,35],[23,36],[23,37],[23,38],[23,39],[23,40],[23,41],[23,42],[23,43],[23,44],[23,45]
[24,30],[24,31],[24,32],[24,33],[24,34],[24,35],[24,36],[24,37],[24,38],[24,39],[24,40],[24,41],[24,42],[24,43],[24,44],[24,45]
[25,30],[25,31],[25,32],[25,33],[25,34],[25,35],[25,36],[25,37],[25,38],[25,39],[25,40],[25,41],[25,42],[25,43],[25,44],[25,45]
[26,30],[26,31],[26,32],[26,33],[26,34],[26,35],[26,36],[26,37],[26,38],[26,39],[26,40],[26,41],[26,42],[26,43],[26,44],[26,45]
[27,30],[27,31],[27,32],[27,33],[27,34],[27,35],[27,36],[27,37],[27,38],[27,39],[27,40],[27,41],[27,42],[27,43],[27,44],[27,45]
[28,30],[28,31],[28,32],[28,33],[28,34],[28,35],[28,36],[28,37],[28,38],[28,39],[28,40],[28,41],[28,42],[28,43],[28,44],[28,45]
[29,30],[29,31],[29,32],[29,33],[29,34],[29,35],[29,36],[29,37],[29,38],[29,39],[29,40],[29,41],[29,42],[29,43],[29,44],[29,45]

[30,1],[30,2],[30,3],[30,4],[30,5],[30,6],[30,7],[30,8],[30,9],[30,10],[30,11],[30,12],[30,13],[30,14],[30,15]
[31,1],[31,2],[31,3],[31,4],[31,5],[31,6],[31,7],[31,8],[31,9],[31,10],[31,11],[31,12],[31,13],[31,14],[31,15]
[32,1],[32,2],[32,3],[32,4],[32,5],[32,6],[32,7],[32,8],[32,9],[32,10],[32,11],[32,12],[32,13],[32,14],[32,15]
[33,1],[33,2],[33,3],[33,4],[33,5],[33,6],[33,7],[33,8],[33,9],[33,10],[33,11],[33,12],[33,13],[33,14],[33,15]
[34,1],[34,2],[34,3],[34,4],[34,5],[34,6],[34,7],[34,8],[34,9],[34,10],[34,11],[34,12],[34,13],[34,14],[34,15]
[35,1],[35,2],[35,3],[35,4],[35,5],[35,6],[35,7],[35,8],[35,9],[35,10],[35,11],[35,12],[35,13],[35,14],[35,15]
[36,1],[36,2],[36,3],[36,4],[36,5],[36,6],[36,7],[36,8],[36,9],[36,10],[36,11],[36,12],[36,13],[36,14],[36,15]
[37,1],[37,2],[37,3],[37,4],[37,5],[37,6],[37,7],[37,8],[37,9],[37,10],[37,11],[37,12],[37,13],[37,14],[37,15]
[38,1],[38,2],[38,3],[38,4],[38,5],[38,6],[38,7],[38,8],[38,9],[38,10],[38,11],[38,12],[38,13],[38,14],[38,15]
[39,1],[39,2],[39,3],[39,4],[39,5],[39,6],[39,7],[39,8],[39,9],[39,10],[39,11],[39,12],[39,13],[39,14],[39,15]
[40,1],[40,2],[40,3],[40,4],[40,5],[40,6],[40,7],[40,8],[40,9],[40,10],[40,11],[40,12],[40,13],[40,14],[40,15]
[41,1],[41,2],[41,3],[41,4],[41,5],[41,6],[41,7],[41,8],[41,9],[41,10],[41,11],[41,12],[41,13],[41,14],[41,15]
[42,1],[42,2],[42,3],[42,4],[42,5],[42,6],[42,7],[42,8],[42,9],[42,10],[42,11],[42,12],[42,13],[42,14],[42,15]
[43,1],[43,2],[43,3],[43,4],[43,5],[43,6],[43,7],[43,8],[43,9],[43,10],[43,11],[43,12],[43,13],[43,14],[43,15]
[44,1],[44,2],[44,3],[44,4],[44,5],[44,6],[44,7],[44,8],[44,9],[44,10],[44,11],[44,12],[44,13],[44,14],[44,15]
[45,1],[45,2],[45,3],[45,4],[45,5],[45,6],[45,7],[45,8],[45,9],[45,10],[45,11],[45,12],[45,13],[45,14],[45,15]

Je pense que les sommets de $1$ à $15$ ont chacun $20$ voisins et $19$ second voisins, les sommets de $16$ à $29$ ont chacun $16$ voisins et $15$ second voisins, et que les sommets de $30$ à $45$ ont chacun $15$ voisins et $14$ second voisins.
Comme d'habitude, je compte à partir d'un graphe schématisé... Bonne vérification et merci.

Ben, j'avais hier travaillé sur un graphe qui était finalement de $177$ sommets. L'erreur d'appréciation que j'avais pas vue et la précipitation m'ont fait poster ce précédent que je trouvais beaucoup plus facile.
Alors celui que je vais te proposer (le graphe d'ordre $177$), a un schéma carrément plus flou, mais j'espèrerais quand mème que le compte soit bon. Je m'attèle à la saisie.
Merci d'avance pour la vérification.

Tu as peut-être bien raison. J'avais encore fait une erreur de comptage.

Mais que représente N dans ton programme ?

certes