Odd graph
Family of symmetric graphs which generalize the Petersen graph
title: "Odd graph" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["parametric-families-of-graphs", "regular-graphs"] description: "Family of symmetric graphs which generalize the Petersen graph" topic_path: "general/parametric-families-of-graphs" source: "https://en.wikipedia.org/wiki/Odd_graph" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0
::summary Family of symmetric graphs which generalize the Petersen graph ::
::data[format=table title="Infobox graph"]
| Field | Value |
|---|---|
| name | Odd graph |
| image | [[File:Kneser graph KG(5,2).svg |
| image_caption | O_3=KG(5,2) is the Petersen graph |
| vertices | \tbinom {2n-1}{n-1} |
| edges | n\tbinom {2n-1}{n-1}/2 |
| diameter | n-1{{citation |
| last | Biggs |
| doi | 10.1007/BF00148146 |
| issue | 1 |
| journal | Geometriae Dedicata |
| pages | 117–127 |
| title | Automorphic graphs and the Krein condition |
| volume | 5 |
| year | 1976}}. |
| girth | 3 for O_2 |
| 5 for O_3 | |
| 6 otherwise{{citation | |
| last | West |
| contribution | Exercise 1.1.28 |
| edition | 2nd |
| location | Englewood Cliffs, NJ |
| page | 17 |
| publisher | Prentice-Hall |
| title | Introduction to Graph Theory |
| year | 2000}}. |
| properties | Distance-transitive |
| notation | On |
| :: |
| name = Odd graph | image = [[File:Kneser graph KG(5,2).svg|200px]] | image_caption = O_3=KG(5,2) is the Petersen graph | namesake = | vertices = \tbinom {2n-1}{n-1} | edges = n\tbinom {2n-1}{n-1}/2 | automorphisms = | radius = | diameter = n-1{{citation | last = Biggs | first = Norman L. | doi = 10.1007/BF00148146 | issue = 1 | journal = Geometriae Dedicata | pages = 117–127 | title = Automorphic graphs and the Krein condition | volume = 5 | year = 1976}}. | girth = 3 for O_2 5 for O_3 6 otherwise{{citation | last = West | first = Douglas B. | author-link = Douglas West (mathematician) | contribution = Exercise 1.1.28 | edition = 2nd | location = Englewood Cliffs, NJ | page = 17 | publisher = Prentice-Hall | title = Introduction to Graph Theory | year = 2000}}. | chromatic_number = | chromatic_index = | properties = Distance-transitive | notation = On ::figure[src="https://upload.wikimedia.org/wikipedia/commons/d/d1/Odd_graph_O4.svg" caption="The odd graph O_4=KG(7,3)"] ::
In the mathematical field of graph theory, the odd graphs are a family of symmetric graphs defined from certain set systems. They include and generalize the Petersen graph.
The odd graphs have high odd girth, meaning that they contain long odd-length cycles but no short ones. However their name comes not from this property, but from the fact that each edge in the graph has an "odd man out", an element that does not participate in the two sets connected by the edge.
Definition and examples
The odd graph O_n has one vertex for each of the (n-1)-element subsets of a (2n-1)-element set. Two vertices are connected by an edge if and only if the corresponding subsets are disjoint. That is, O_n is the Kneser graph KG(2n-1,n-1).
O_2 is a triangle, while O_3 is the familiar Petersen graph.
The generalized odd graphs are defined as distance-regular graphs with diameter n-1 and odd girth 2n-1 for some n. They include the odd graphs and the folded cube graphs.
History and applications
Although the Petersen graph has been known since 1898, its definition as an odd graph dates to the work of , who also studied the odd graph O_4.{{citation | last = Kowalewski | first = A. | journal = Sitzungsber. Akad. Wiss. Wien (Abt. IIA) | pages = 67–90, 963–1007 | title = W. R. Hamilton's Dodekaederaufgabe als Buntordnungproblem | volume = 126 | year = 1917}}. As cited by . Odd graphs have been studied for their applications in chemical graph theory, in modeling the shifts of carbonium ions.{{citation | last1 = Balaban | first1 = Alexandru T. | last2 = Fǎrcaşiu | first2 = D. | last3 = Bǎnicǎ | first3 = R. | journal = Rev. Roum. Chim. | page = 1205 | title = Graphs of multiple 1, 2-shifts in carbonium ions and related systems | volume = 11 | year = 1966}}.{{citation | last = Balaban | first = Alexandru T. | journal = Rev. Roumaine Math. Pures Appl. | pages = 3–16 | title = Chemical graphs, Part XIII: Combinatorial patterns | volume = 17 | year = 1972}}. They have also been proposed as a network topology in parallel computing.{{citation | last1 = Ghafoor | first1 = Arif | last2 = Bashkow | first2 = Theodore R. | doi = 10.1109/12.73594 | issue = 2 | journal = IEEE Transactions on Computers | pages = 225–232 | title = A study of odd graphs as fault-tolerant interconnection networks | volume = 40 | year = 1991 | bibcode = 1991ITCmp..40..225G
The notation O_n for these graphs was introduced by Norman Biggs in 1972.{{citation | last = Biggs | first = Norman | title = An edge-colouring problem | number = 9 | editor-last = Guy | editor-first = Richard K. | editor-link = Richard K. Guy | journal = American Mathematical Monthly | pages = 1018–1020 | department = Research Problems | jstor = 2318076 | doi = 10.2307/2318076 | volume = 79 | year = 1972}}. Biggs and Tony Gardiner explain the name of odd graphs in an unpublished manuscript from 1974: each edge of an odd graph can be assigned the unique element which is the "odd man out", i.e., not a member of either subset associated with the vertices incident to that edge.{{citation | last1 = Brouwer | first1 = Andries | author1-link = Andries Brouwer | last2 = Cohen | first2 = Arjeh M. | last3 = Neumaier | first3 = A. | isbn = 0-387-50619-5 | title = Distance-regular Graphs | year = 1989 | publisher = Springer }}.{{citation | last = Ed Pegg | first = Jr. | author-link = Ed Pegg, Jr. | date = December 29, 2003 | publisher = Mathematical Association of America | series = Math Games | title = Cubic Symmetric Graphs | url = http://maa.org/editorial/mathgames/mathgames_12_29_03.html | access-date = August 24, 2010 | archive-url = https://web.archive.org/web/20100821184232/http://www.maa.org/editorial/mathgames/mathgames_12_29_03.html | archive-date = August 21, 2010 | url-status = dead
Properties
The odd graph O_n is regular of degree n. It has \tbinom {2n-1}{n-1} vertices and n\tbinom {2n-1}{n-1}/2 edges. Therefore, the number of vertices for n=1,2,\dots is
Distance and symmetry
If two vertices in O_n correspond to sets that differ from each other by the removal of k elements from one set and the addition of k different elements, then they may be reached from each other in 2k steps, each pair of which performs a single addition and removal. If 2k, this is a shortest path; otherwise, it is shorter to find a path of this type from the first set to a set complementary to the second, and then reach the second set in one more step. Therefore, the diameter of O_n is n-1.
Every odd graph is 3-arc-transitive: every directed three-edge path in an odd graph can be transformed into every other such path by a symmetry of the graph. Odd graphs are distance transitive, hence distance regular. As distance-regular graphs, they are uniquely defined by their intersection array: no other distance-regular graphs can have the same parameters as an odd graph.{{citation | last = Moon | first = Aeryung | doi = 10.1016/0012-365X(82)90057-7 | issue = 1 | journal = Discrete Mathematics | pages = 91–97 | title = Characterization of the odd graphs Ok by parameters | volume = 42 | year = 1982| doi-access = free | last = Godsil | first = C. D. | doi = 10.1016/0012-365X(80)90055-2 | issue = 2 | journal = Discrete Mathematics | pages = 205–207 | title = More odd graph theory | volume = 32 | year = 1980| doi-access = free
Because odd graphs are regular and edge-transitive, their vertex connectivity equals their degree, n.{{citation | last = Watkins | first = Mark E. | doi = 10.1016/S0021-9800(70)80005-9 | journal = Journal of Combinatorial Theory | mr = 266804 | pages = 23–29 | title = Connectivity of transitive graphs | volume = 8 | year = 1970| doi-access =
Odd graphs with n3 have girth six; however, although they are not bipartite graphs, their odd cycles are much longer. Specifically, the odd graph O_n has odd girth 2n-1. If an n-regular graph has diameter n-1 and odd girth 2n-1, and has only n distinct eigenvalues, it must be distance-regular. Distance-regular graphs with diameter n-1 and odd girth 2n-1 are known as the generalized odd graphs, and include the folded cube graphs as well as the odd graphs themselves.{{citation | last1 = Van Dam | first1 = Edwin | last2 = Haemers | first2 = Willem H. | series = CentER Discussion Paper Series No. 2010-47 | title = An Odd Characterization of the Generalized Odd Graphs | ssrn = 1596575 | year = 2010}}.
Independent sets and vertex coloring
Let O_n be an odd graph defined from the subsets of a (2n-1)-element set X, and let x be any member of X. Then, among the vertices of O_n, exactly \tbinom{2n-2}{n-2} vertices correspond to sets that contain x. Because all these sets contain x, they are not disjoint, and form an independent set of O_n. That is, O_n has 2n-1 different independent sets of size \tbinom{2n-2}{n-2}. It follows from the Erdős–Ko–Rado theorem that these are the maximum independent sets of O_n, i.e. the independence number of O_n is \tbinom{2n-2}{n-2}. Further, every maximum independent set must have this form, so O_n has exactly 2n-1 maximum independent sets.
If I is a maximum independent set, formed by the sets that contain x, then the complement of I is the set of vertices that do not contain x. This complementary set induces a matching in G. Each vertex of the independent set is adjacent to n vertices of the matching, and each vertex of the matching is adjacent to n-1 vertices of the independent set. Because of this decomposition, and because odd graphs are not bipartite, they have chromatic number three: the vertices of the maximum independent set can be assigned a single color, and two more colors suffice to color the complementary matching.
Edge coloring
By Vizing's theorem, the number of colors needed to color the edges of the odd graph O_n is either n or n+1, and in the case of the Petersen graph O_3 it is n+1. When n is a power of two, the number of vertices in the graph is odd, from which it again follows that the number of edge colors is n+1.{{citation | last1 = Meredith | first1 = Guy H. J. | last2 = Lloyd | first2 = E. Keith | doi = 10.1016/0095-8956(73)90016-6 | journal = Journal of Combinatorial Theory, Series B | pages = 161–166 | title = The footballers of Croam | volume = 15 | issue = 2 | year = 1973| doi-access =
Biggs explains this problem with the following story, about the "footballers of Croam": eleven soccer players in the fictional town of Croam wish to form up pairs of five-man teams (with an odd man out to serve as referee) in all 1386 possible ways, and they wish to schedule the games between each pair in such a way that the six games for each team are played on six different days of the week, with Sundays off for all teams. Is it possible to do so? In this story, each game represents an edge of O_6, each weekday is represented by a color, and a 6-color edge coloring of O_6 provides a solution to the players' scheduling problem.
Hamiltonicity
The Petersen graph O_3 is a well known non-Hamiltonian graph, but all odd graphs O_n for n\ge 4 are known to have a Hamiltonian cycle.{{citation | last1 = Mütze | first1 = Torsten | last2 = Nummenpalo | first2 = Jerri | last3 = Walczak | first3 = Bartosz | arxiv = 1711.01636 | mr = 4273468 | pages = 1253–1275 | title = Sparse Kneser graphs are Hamiltonian | journal = Journal of the London Mathematical Society | year = 2018 | volume = 103 | issue = 4 | doi = 10.1112/jlms.12406 As the odd graphs are vertex-transitive, they are thus one of the special cases with a known positive answer to Lovász' conjecture on Hamiltonian cycles in vertex-transitive graphs. Biggs conjectured more generally that the edges of O_n can be partitioned into \lfloor n/2\rfloor edge-disjoint Hamiltonian cycles. When n is odd, the leftover edges must then form a perfect matching. This stronger conjecture was verified for n=4,5,6,7. For n=8, the odd number of vertices in O_n prevents an 8-color edge coloring from existing, but does not rule out the possibility of a partition into four Hamiltonian cycles.
References
References
- Babai, László. (1995). "Handbook of Combinatorics". North-Holland.
- Biggs, Norman. (1979). "Some odd graph theory". Annals of the New York Academy of Sciences.
::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::