Longueur de chemin dans un graphe d'ordre n

Ch4rstz

Si j'ai un graphe G orienté d'ordre n. Est-ce que l'implication suivante est vraie : 

"Si j'ai un chemin reliant le sommet i et le sommet j à n + k arcs alors j'ai un chemin reliant les sommets i et j à moins de n arcs."

Ch4rstz

Mon intuition est la suivante : 

Si je regarde  les (n-1) premiers arcs de ce chemin alors forcément j'ai un sommet qui a été répété deux fois.
Si c'est le sommet qui correspond à l'extrémité initiale de mon chemin alors j'ai fini puisque la répétition se fait forcément dans une extrémité terminale d'un autre arc que le premier.
Si c'est un autre sommet alors c'est comme si j'avais fais un "trajet inutile" puisque j'ai fais un cycle dont je pouvais a priori sortir (sinon ce serait infini) pour rejoindre l'extrémité initiale de mon chemin. 
Mettons que je supprime tout les cycles de mon chemin (ça reste un chemin de i à j). Qu'est ce que je peux en déduire sur mes arcs ? Si je regarde par exemple, l'extremité terminale de mon premier arc alors comme j'ai interdis les cycles elle ne peut plus réapparaitre et ainsi de suite. Ainsi, après mon premier arc j'ai (n-2) options de sommets avant l'arc conclusif de mon chemin après le troisième j'en aurais (n-3) et donc après n arcs j'en aurais 0 et je ne pourrais pas avancer et comme je dois placer mon sommet conclusif c'est impossible donc j'ai forcément un chemin qui implique au plus n arcs.

Cela vous parait correct ?

lourrran

ça paraît vraiment lourdingue comme explication.
Le résultat que tu cherches à démontrer est un résultat exact. 
L'idée est évidement que les cycles peuvent être supprimés, et que tout chemin qui passe par plus de $n$ points contient forcément au moins un cycle.