# L'admissibilité des contractions : 383 des 384 patchs C établis

## Contexte

Le lemme général des contractions (`4CT_corpus_complet.md`, §5) exige trois
hypothèses pour transférer une 4-coloration du quotient G/q vers le graphe
original G :

1. G/q a strictement moins de sommets que G — vrai par construction ;
2. **aucune arête de l'extérieur H, bord compris, n'a ses deux extrémités
   identifiées par la contraction q** ;
3. toute coloration de bord induite par G/q est couverte par un certificat
   déjà établi.

L'hypothèse 3 est vérifiée informatiquement pour les 384 patchs C
(`independent_summary.json` : `contract_intersection: 0` sur les 2 200 962
frontières de contrat). L'hypothèse 2, en revanche, n'avait été traitée
qu'une seule fois, à la main, pour le patch 2.126 : « les identifications
sont {1,3,u} et {5,7,v} [...] un contre-exemple minimal ne possède pas de
triangle séparateur ». Rien n'indiquait si cet argument se généralisait, ni
combien des 383 autres patchs C en avaient réellement besoin.

## Lemme (purement combinatoire, sans hypothèse topologique)

**Énoncé.** Soit q une contraction de P, dont les classes d'équivalence
(les groupes de sommets identifiés ensemble) sont G₁, …, Gₖ. Si chaque
groupe Gᵢ contient **au plus un** sommet de bord de P, alors l'hypothèse 2
est automatiquement satisfaite — quelle que soit l'arête considérée et
quelle que soit l'occurrence de P dans un graphe ambiant.

**Preuve.** Une arête de H a nécessairement au moins une extrémité qui est
un sommet de bord de P : les arêtes entièrement extérieures à P (les deux
extrémités hors de P) ne sont pas affectées par q, qui n'agit que sur
V(P) — un sommet hors de P n'est identifié à rien. Pour qu'une arête de H
ait ses **deux** extrémités identifiées par q, il faut donc que ses deux
extrémités soient toutes deux des sommets de bord de P, et qu'elles tombent
dans le même groupe Gᵢ. Si aucun groupe ne contient deux sommets de bord
distincts, cette situation ne peut jamais se produire. ∎

Ce lemme ne fait appel à aucun fait sur les contre-exemples minimaux : c'est
une conséquence directe de la définition de q et de la structure de H. Il
se vérifie mécaniquement sur les données du corpus, sans plongement
particulier.

## Vérification sur les 384 patchs C

Pour chaque patch C, les groupes de q sont les composantes connexes du
graphe formé par `contract_edges` (deux sommets sont dans le même groupe
s'ils sont reliés, directement ou par une chaîne, par une arête contractée).
Script : `experiments/contraction_admissibility.py`, vérifié par une
seconde implémentation indépendante (union-find distincte, 0 écart).

```
C patches: 384
trivial (lemme ci-dessus) : 307
nécessite un argument topologique : 77
```

| Sommets de bord par groupe | Nb de groupes | |
| --- | --- | --- |
| 0 | 289 | hypothèse 2 automatique (aucun sommet de bord dans le groupe) |
| 1 | 39 | hypothèse 2 automatique |
| 2 | 96 | risque réel — nécessite l'argument topologique |
| 3 | 8 | risque réel, trois arêtes à exclure |

**307 des 384 patchs C (80 %) satisfont donc l'hypothèse 2 sans aucun
argument topologique**, par un simple fait combinatoire sur leurs groupes
de contraction. C'est un résultat nouveau : le manuscrit ne l'avait établi
que pour un seul patch (2.126), et 2.126 fait justement partie des 77
patchs *non* couverts par ce lemme (ses deux groupes ont chacun 2 sommets
de bord).

## Les 77 patchs restants

Pour ces patchs, au moins un groupe contient 2 ou 3 sommets de bord : le
lemme ci-dessus ne s'applique pas, et il faut un argument topologique sur
le contre-exemple minimal (du type de celui écrit pour 2.126) pour exclure
l'existence de la corde dangereuse dans H.

L'écart cyclique entre les sommets de bord d'un même groupe (sur les 120
paires à risque, issues des 96 groupes à 2 sommets de bord et des 8
groupes à 3, qui fournissent chacun 3 paires) se répartit ainsi :

| Écart cyclique | Nb de paires |
| --- | --- |
| 2 | 97 |
| 3 | 2 |
| 4 | 8 |
| 5 | 4 |
| 6 | 8 |
| 7 | 1 |

## L'argument du triangle généralisé : 58 patchs de plus

Pour une paire (i, j) de sommets de bord d'écart cyclique 2, de sommet
médian m (l'unique sommet de bord strictement entre i et j), l'argument
écrit pour 2.126 se généralise **si et seulement si** :

**(a)** il existe un sommet u de P adjacent à la fois à i et à j dans P —
peu importe que u appartienne ou non au même groupe de contraction que i
et j, seule l'adjacence réelle dans P compte. Le triangle i–u–j utilise
alors des arêtes réelles de P (exactement comme 1–9–3 pour 2.126, avec
u = 9, qui est bien le sommet auquel 1 et 3 sont identifiés — mais ce
n'est pas une nécessité de l'argument, seulement le cas de 2.126).

**(b)** m n'a **aucun** autre voisin dans P que i, j et u — ses voisins
(donnés par `adj`) forment exactement {i, j, u}.

**Preuve, si (a) et (b) tiennent.** Si l'arête i–j existait dans H, le
cycle i–u–j–i serait un triangle du graphe complet G = P ∪ H (les arêtes
i–u et u–j sont réelles par (a), l'arête i–j serait celle de H). Par (b),
m n'a de voisins que parmi {i, j, u} : retirer ces trois sommets isole m
de tout le reste de G. Le triangle i–u–j sépare donc m du reste du graphe.
Or un contre-exemple minimal ne possède pas de triangle séparateur : soient
G₁ et G₂ les deux côtés du triangle (chacun contenant les 3 sommets du
triangle), tous deux strictement plus petits que G, donc 4-coloriables par
minimalité ; une permutation des 4 couleurs d'un côté fait coïncider ses
couleurs sur le triangle avec celles de l'autre côté (le triangle impose 3
couleurs distinctes parmi 4, et toute permutation amenant un triplet
ordonné sur un autre existe) ; les deux colorations se recollent en une
coloration propre de G entier, contredisant que G est un contre-exemple.
L'arête i–j ne peut donc pas exister. ∎

C'est exactement l'argument de 2.126, avec u et m à la place de 9 et 2 —
aucune nouveauté mathématique, seulement sa vérification mécanique sur
toutes les paires candidates.

**Vérification** (`experiments/triangle_argument_generalization.py`,
ré-implémentation indépendante, 0 écart) sur les 120 paires à risque :

```
paires à écart 2 : 97
  résolues par l'argument généralisé : 97
paires à écart > 2 : 23 (hors du champ de cet argument, non résolues)

patchs C non triviaux : 77
  entièrement résolus par la généralisation : 58
  encore ouverts : 19
```

**Les 97 paires à écart 2, sans exception, se résolvent par l'argument
généralisé.** Une première version de cette vérification cherchait le
sommet u uniquement parmi les membres du même groupe de contraction que i
et j (en suivant la chaîne dans `contract_edges`), et ne trouvait ainsi de
témoin que pour 91 d'entre elles. C'était une restriction artificielle :
rien dans l'argument n'exige que u soit lui-même identifié à quoi que ce
soit — seule son adjacence réelle à i et j dans P compte. En cherchant u
parmi tous les sommets de P, les 6 paires restantes se résolvent aussi
(par exemple pour `128.136`, paire (1,10) : le sommet 16, non contracté,
est adjacent à la fois à 1 et à 10, et le sommet médian 11 n'a effectivement
aucun autre voisin que {1, 10, 16}).

**TOTAL : 365 des 384 patchs C (95 %) ont désormais l'hypothèse 2
établie** — 307 par le lemme combinatoire pur, 58 de plus par la
généralisation vérifiée de l'argument du triangle de 2.126. Le compte de
patchs ne change pas par rapport à la version précédente de cette
vérification (58/19 dans les deux cas), parce que les 19 patchs encore
ouverts le sont tous à cause d'au moins une paire à écart **strictement
supérieur à 2** — un problème distinct, hors du champ de cet argument, et
non parce qu'une de leurs paires à écart 2 résistait.

## Les 23 paires à écart > 2 : un raccourci intérieur change la donne

Pour ces 23 paires, le plus court chemin *le long du bord* a bien pour
longueur l'écart (3 à 7) — mais ce n'est pas le plus court chemin dans P
tout entier. En cherchant un chemin i–...–j qui ne passe par **aucun
autre sommet de bord** (donc un vrai raccourci par l'intérieur, pas
l'arc du bord lui-même), on trouve systématiquement un chemin bien plus
court : **12 paires** donnent un raccourci à 2 arêtes (donc un
**triangle** une fois fermé par l'arête hypothétique), **11 paires** un
raccourci à 3 arêtes (un **quadrilatère**).

Script : `experiments/triangle_shortcut_argument.py`, vérifié
indépendamment (0 écart). Pour les 12 cas de raccourci triangulaire,
la séparation effective de l'arc « between » (les sommets de bord
strictement entre i et j) a été vérifiée par calcul de composantes
connexes après retrait du chemin — exactement comme pour l'écart 2.

### Les 12 triangles : même argument, aucune nouveauté

Un triangle séparateur, quelle que soit la taille du côté qu'il isole (un
seul sommet ou plusieurs), reste exclu par le **même** argument
élémentaire que pour 2.126 : un contre-exemple minimal n'en a pas, par
permutation de couleurs entre les deux côtés. **10 des 19 patchs
restants n'ont QUE des paires qui se résolvent ainsi** (leurs autres
paires à risque, s'il y en a, sont déjà couvertes par le lemme
combinatoire ou l'argument à écart 2) :

```
126.442802  126.1306802  126.687602  126.1551602  126.3682802
126.3686402 7322.453720  7562.460920 7562.1307280 7562.1310580
```

**TOTAL : 375 des 384 patchs C (98 %) ont désormais l'hypothèse 2
établie** — 307 par le lemme combinatoire, 58 par l'écart 2, 10 de plus
par ce raccourci triangulaire à écart > 2. (8 autres s'y ajoutent avec une
contraction de remplacement, `4CT_contractions_de_remplacement.md`, soit 383 des 384.)

### Les 11 quadrilatères : un argument différent, non fait ici

Pour les 9 patchs restants, au moins une paire ne donne qu'un
quadrilatère séparateur, pas un triangle. **Ce n'est pas le même
argument, et je ne l'ai pas démontré.** La raison précise : un triangle
n'a qu'un seul « profil » de coloration possible, puisque ses trois
sommets sont mutuellement adjacents — n'importe quelle 4-coloration lui
donne 3 couleurs distinctes, et deux triplets de couleurs distinctes se
correspondent toujours par une permutation des 4 couleurs. Un
quadrilatère, lui, a des sommets opposés **non adjacents** : une
4-coloration peut leur donner la même couleur ou des couleurs
différentes, ce qui crée plusieurs profils possibles (2, 3 ou 4 couleurs
utilisées) qu'une simple permutation ne suffit pas à faire coïncider en
général. Exclure un quadrilatère séparateur demande un argument de
**chaînes de Kempe** : recolorier un des deux côtés le long d'une
composante bicolore pour changer le profil de coloration de son bord
sans toucher au reste — une technique standard mais nettement plus
délicate que la permutation directe, que je n'ai pas menée à bien ici.

### Tentative de preuve autonome par chaînes de Kempe : pourquoi elle échoue

Une tentative sérieuse a été faite pour écrire l'argument des chaînes de
Kempe comme preuve autonome (sur le modèle de celle du triangle), sans
succès. Voici précisément où ça bloque, pour que la difficulté soit
vérifiable plutôt qu'affirmée.

Soit C = i–u1–u2–j le quadrilatère, G1 le côté « between » (isolé,
petit), G2 l'autre côté (le reste d'un contre-exemple minimal
hypothétique, par définition non accessible dans ce corpus). Une
4-coloration propre de C a l'un de 4 profils selon que chaque paire de
sommets opposés (i,u2) et (u1,j) — non adjacents, contrairement aux
sommets d'un triangle — reçoit la même couleur ou non. Recoller φ1 et φ2
exige que leurs profils coïncident **exactement sur les deux diagonales
à la fois**, pas seulement sur une.

Une chaîne de Kempe (recoloration d'une composante bicolore) permet
toujours de forcer **une** des deux diagonales à coïncider (par un
argument de planarité : si un chemin bicolore relie déjà i à u2 dans un
côté, alors aucun chemin dans les deux autres couleurs ne peut relier u1
à j dans ce même côté, ce qui autorise l'échange sur cette seconde
diagonale à la place). Mais forcer les **deux simultanément** n'est pas
automatique, et un second échange peut défaire ou ne pas pouvoir corriger
le premier resultat.

Pire : les profils réellement atteignables ne sont pas librement
choisissables — ils dépendent de la structure précise de chaque côté.
Contre-exemple explicite : pour une roue (un sommet central adjacent aux
quatre sommets du cycle), le profil « quatre couleurs distinctes sur le
cycle » est structurellement impossible (il ne resterait aucune couleur
disponible pour le centre). Rien ne garantit donc que les ensembles de
profils atteignables par G1 et par G2 se recoupent.

Une piste plus solide existe (récurer par contraction — identifier i et
u2, colorier le graphe réduit, sur le modèle exact du lemme des
contractions §5 de ce document — appliquée récursivement des deux
côtés), mais elle demande une seconde couche d'argument distincte, non
menée à son terme ici. J'ai vérifié (`experiments/triangle_shortcut_summary.json`,
champ `quadrilateral_pairs`) qu'aucun des 11 cas ne bénéficie d'une
simplification structurelle évidente : aucune des deux diagonales
(i–u2 ou u1–j) n'est une arête réelle de P, qui aurait forcé un profil
unique et simplifié la reconciliation.

## Les 9 patchs encore ouverts

```
128.136  126.8168  140.8406  126.62942  8406.123
7696.442802  7877.442802  8406.363  439328.136
```

Chacun a au moins une paire à écart > 2 dont le raccourci intérieur est un
quadrilatère, pas un triangle. `atlas_data.json` porte, par patch C, le
champ `contraction_admissibility.resolved_by_interior_triangle_shortcut`
(faux pour ces 9).

*Mise à jour : 8 de ces 9 patchs sont désormais établis par une
contraction de remplacement (`4CT_contractions_de_remplacement.md`). Le paragraphe
suivant ne vaut plus que pour 126.62942.*

**Statut retenu pour ces 9 cas : citation, pas preuve.** Comme ce
document le fait déjà pour l'inévitabilité (§9 de `4CT_corpus_complet.md` :
« résultat historique distinct », non recalculé), ces 9 patchs s'appuient
sur la **6-connexité interne des contre-exemples minimaux**, un résultat
structurel classique et établi de la littérature RSST/Appel-Haken (les
contre-exemples minimaux n'ont pas de cycle séparateur non facial de
longueur ≤ 5, ce qui couvre triangles et quadrilatères). Ce n'est **pas**
une preuve autonome comme celle donnée ci-dessus pour le triangle — c'est
une hypothèse externe, dont la validité pour la construction précise de
ce corpus (occurrences fidèles des patchs dans un plongement réel) reste
à vérifier avant de considérer ces 9 cas comme réellement clos, exactement
comme le document le note déjà pour 2.126 : « il reste toujours à
justifier les trois hypothèses dans le contexte d'occurrence du patch ».

## Portée

L'hypothèse 2 du lemme des contractions est établie par une **preuve
autonome, explicite et vérifiée mécaniquement**, sans aucune hypothèse
topologique non prouvée ici, pour **383 des 384 patchs C** : 375 avec la
contraction historique, 8 avec une contraction de remplacement
(`4CT_contractions_de_remplacement.md`). Pour le **dernier patch, 126.62942**, elle repose sur une
**citation** de la littérature (6-connexité interne), non re-démontrée dans
ce document.

## Tentative 2 : le petit côté connu réalise les 4 profils — pourquoi ça ne suffit pas

Idée testée (`experiments/quadrilateral_diagonal_profiles.py`) : plutôt que de
faire porter l'argument de Kempe sur *les deux* côtés du quadrilatère
séparateur, ne le faire porter que sur un seul — le côté « between »,
c'est-à-dire le petit morceau isolé par le raccourci intérieur i–u1–u2–j.
Ce morceau est un graphe **fini et entièrement connu** (sous-graphe induit
de P, entre 6 et 14 sommets selon les 11 paires). S'il réalisait, à lui
seul, les 4 profils possibles de coloration du quadrilatère (i=u2 et/ou
u1=j, ou aucun des deux), alors peu importerait le profil produit par une
coloration de l'autre côté (inconnu) : une simple permutation des 4
couleurs suffirait à les faire coïncider, sans aucune chaîne de Kempe.

**Résultat de la vérification** (deux méthodes de coloriage indépendantes
— backtracking ordonné et énumération brute par produit cartésien filtré,
comparées terme à terme, 0 écart sur les 9 paires où l'énumération brute
est praticable) : **les 11 paires réalisent bien les 4 profils** sur cette
partie connue, sans exception.

**Pourquoi ça ne clôt pas les 9 patchs.** Ce graphe connu n'est qu'une
*partie* du véritable petit côté. Le §2 de `4CT_corpus_complet.md` est
explicite : « tous les voisins des sommets **strictement intérieurs** sont
décrits par P » — pas ceux des sommets de bord. Un contre-exemple minimal
est une triangulation de degré minimum ≥ 5 (fait élémentaire standard : un
sommet de degré ≤ 4 donnerait immédiatement une configuration réductible
plus simple), donc tout sommet de bord dont le degré *au sein de P seul*
est inférieur à 5 a nécessairement des arêtes supplémentaires vers H, non
décrites ici. Vérification : **dans les 11 paires, sans exception, tous
les sommets de bord du côté « between » ont un degré dans P strictement
inférieur à 5** (3 ou 4) :

```
128.136 (gap 4)       : sommets 1,2,11  — degrés 4,3,3
126.8168 (gap 3)      : sommets 7,8     — degrés 4,3
126.8168 (gap 5)      : sommets 7,8,9,10 — degrés 4,3,4,3
140.8406 (gap 4)      : sommets 3,4,5   — degrés 3,4,3
126.62942 (gap 5)     : sommets 2,3,4,5 — degrés 4,3,4,3
8406.123 (gap 4)      : sommets 2,3,4   — degrés 3,4,3
7696.442802 (gap 6)   : sommets 9,11,12,13 — degrés 3,4,3,4 (sommet 10 seul a déjà 5)
8406.363 (gap 4)      : sommets 2,3,4   — degrés 3,4,3
7877.442802 (gap 3)   : sommets 2,3     — degrés 3,4
7877.442802 (gap 7)   : sommets 5,6,7,8,9,10 — degrés 3,4,3,4,4,3
439328.136 (gap 4)    : sommets 1,2,13  — degrés 4,3,3
```

Le petit côté réel inclut donc, en plus de ce graphe connu, une structure
H cachée et inconnue attachée à ces sommets de bord. Une coloration du
graphe connu réalisant un profil donné n'a aucune raison de s'étendre à
cette structure cachée : établir que la partie visible réalise les 4
profils ne dit rien sur ce que réalise le petit côté complet. C'est
exactement la même difficulté que pour la tentative précédente (faire
coïncider deux côtés partiellement inconnus n'est pas automatique) — cette
piste locale ne la contourne pas, elle ne fait que déplacer le problème
d'un côté du quadrilatère vers l'autre.

## Piste ouverte : contraction récursive sur une diagonale

Une direction distincte, non aboutie ici, évite complètement le problème
de raccord de profils. Elle repose sur une observation combinatoire pure :
**u1 et u2 sont des sommets strictement intérieurs de P** (ce sont les
sommets du raccourci, jamais des sommets de bord — sinon le raccourci
serait lui-même un chemin de bord). Par le §2, tous leurs voisins sont
décrits par P : ils n'ont, par construction, **aucune arête vers H**.

Conséquence : la contraction q' qui identifie seulement {i, u2} (une
diagonale du quadrilatère) forme un groupe avec **au plus un** sommet de
bord (i ; u2 n'en est pas un). Le lemme déjà établi plus haut dans ce même
document (« si chaque groupe contient au plus un sommet de bord, l'hypothèse
2 est automatique ») s'applique donc *sans aucun calcul supplémentaire* :
q' satisfait trivialement l'hypothèse 2. (Même chose pour la diagonale
symétrique {u1, j}.)

Si G/q' était un contre-exemple minimal, il serait 4-coloriable (moins de
sommets que G). Si l'hypothèse 3 de q' — les colorations de bord induites
par G/q' sont couvertes par un certificat de fermeture — pouvait aussi être
vérifiée, le lemme des contractions (§5 du corpus complet) donnerait
directement une 4-coloration de G, contredisant sa minimalité. **Ce n'est
pas fait ici** : contrairement à q, la contraction q' est nouvelle (jamais
utilisée dans les 384 contrats historiques de ce corpus) et identifie un
sommet de bord à un sommet intérieur, ce qui change la forme du bord
résultant — vérifier son hypothèse 3 demande d'adapter le solveur de
fermeture par échanges (§4 du corpus complet) à ce nouveau bord, pas
seulement de relancer les scripts existants sur les contrats déjà
calculés. C'est un travail de calcul nouveau, distinct de tout ce qui a
été fait jusqu'ici dans ce document. **Il est fait dans
`4CT_contractions_de_remplacement.md`**, sous une forme plus générale
(toutes les contractions dont les paires de bord identifiées sont protégées
par un triangle, la diagonale n'en étant qu'un cas particulier) : 8 des 9
patchs sont établis ; pour le dernier, 126.62942, aucune contraction de ce
type n'existe.

## Contraction de remplacement : 8 des 9 patchs établis

Détail dans `4CT_contractions_de_remplacement.md`. Le lemme des contractions
vaut pour toute contraction d'arêtes de P qui vérifie ses trois hypothèses.
Pour 8 des 9 patchs, une contraction de remplacement convient. Ses groupes
sont connexes, et toutes ses paires de bord identifiées sont non
consécutives avec un voisin intérieur commun, donc protégées par l'argument
du triangle. Aucun mot résiduel n'est réalisé par son quotient. Pour
126.62942, une recherche exhaustive sur toutes les partitions de P en
groupes connexes (7 328 989 candidats) montre qu'aucune contraction de ce
type n'existe.

## Bilan des tentatives

Deux tentatives indépendantes de clore les 9 patchs restants sans citation
ont maintenant été documentées et ont chacune buté sur la même difficulté
de fond, sous deux formes différentes :
- chaînes de Kempe direct sur les deux côtés : les profils atteignables ne
  sont pas garantis coïncider (tentative 1, ci-dessus) ;
- le côté connu réalise tous les profils, mais ce n'est qu'une partie du
  vrai petit côté, à cause des arêtes de bord non décrites par P
  (tentative 2, ci-dessus).

La contraction de remplacement (section précédente) contourne cette
difficulté : elle ne demande la coïncidence d'aucun profil. On choisit une
autre contraction, dont toutes les paires identifiées sont protégées par un
triangle. Elle aboutit pour 8 patchs sur 9. Pour le dernier, la recherche
exhaustive prouve qu'aucune contraction de ce type n'existe. **Statut :
383 des 384 patchs C ont une preuve autonome de l'hypothèse 2. Seul
126.62942 repose encore sur la citation de la 6-connexité interne.**