The Shortest Odd Cycle Is Chordless
A chord of an odd cycle splits it into two cycles, exactly one of which is odd, and both of which are shorter. A shortest odd cycle therefore carries no chord, and the subgraph it induces is exactly itself. Its chromatic number is $3$, whatever the chromatic number of the ambient graph. This is the precise sense in which chromatic number fails to localise to odd cycles: a graph of chromatic number $10^6$ still contains an odd cycle spanning a subgraph of chromatic number $3$, and the witness is available at the shortest one. Girth is a separate and weaker instrument. A chorded cycle has length at least $2g - 2$, so girth forbids chords only below that threshold, and the threshold is attained.
Authors
- Christopher Mills (ORCID: https://orcid.org/0000-0003-0003-0552)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-09-21
- DOI
- https://doi.org/10.5281/zenodo.22883463
- Primary Topic
- Advanced Graph Theory Research
- Type
- preprint