View source for Levi graph

{{Short description|Graph representing incident points and lines}}
{{CS1 config|mode=cs1}}
{{Infobox graph
 | name     = Levi graph
 | image    = [[File:Levi graph of Pappus Configuration.png|frameless]]
 | image_caption = The [[Pappus graph]], a Levi graph with 18 vertices formed from the [[Pappus configuration]]. Vertices labeled with single letters correspond to points in the configuration; vertices labeled with three letters correspond to lines through three points.
 | namesake =
 | vertices =
 | edges    =
 | radius   =
 | diameter =
 | girth    = ≥ 6
 | chromatic_number =
 | chromatic_index  =
 | properties =
}}
In [[combinatorics|combinatorial mathematics]], a '''Levi graph''' or '''incidence graph''' is a [[bipartite graph]] associated with an [[incidence structure]].<ref name="bg">{{cite book
 | last = Grünbaum | first = Branko | author-link = Branko Grünbaum
 | contribution = Configurations of points and lines
 | location = Providence, RI
 | mr = 2209028
 | pages = 179–225
 | publisher = American Mathematical Society
 | title = The Coxeter Legacy
 | year = 2006}}. See in particular [https://books.google.com/books?id=cKpBGcqpspIC&pg=PA181 p. 181].</ref><ref>{{cite book
 | last = Polster | first = Burkard |author-link=Burkard Polster
 | doi = 10.1007/978-1-4419-8526-2
 | isbn = 0-387-98437-2
 | location = New York
 | mr = 1640615
 | page = 5
 | publisher = Springer-Verlag
 | series = Universitext
 | title = A Geometrical Picture Book
 | url = https://books.google.com/books?id=2PtPG4qjfZAC&pg=PA5
 | year = 1998}}.</ref> From a collection of points and lines in an [[incidence geometry]] or a [[projective configuration]], we form a graph with one vertex per point, one vertex per line, and an edge for every incidence between a point and a line. They are named for [[Friedrich Wilhelm Levi]], who wrote about them in 1942.<ref name="bg"/><ref>{{cite book
 | last = Levi | first = F. W. | author-link = Friedrich Wilhelm Levi
 | location = Calcutta
 | mr = 0006834
 | publisher = [[University of Calcutta]]
 | title = Finite Geometrical Systems
 | year = 1942}}.</ref>

The Levi graph of a system of points and lines usually has [[girth (graph theory)|girth]] at least six: Any 4-[[Cycle graph|cycles]] would correspond to two lines through the same two points. Conversely any bipartite graph with girth at least six can be viewed as the Levi graph of an abstract incidence structure.<ref name="bg"/> Levi graphs of configurations are [[biregular graph|biregular]], and every biregular graph with girth at least six can be viewed as the Levi graph of an abstract configuration.<ref>{{cite book
 | last = Gropp | first = Harald
 | editor1-last = Colbourn | editor1-first = Charles J.
 | editor2-last = Dinitz | editor2-first = Jeffrey H.
 | contribution = VI.7 Configurations
 | edition = Second
 | pages = 353–355
 | publisher = Chapman & Hall/CRC, Boca Raton, Florida
 | series = Discrete Mathematics and its Applications (Boca Raton)
 | title = Handbook of combinatorial designs
 | year = 2007}}.</ref>

Levi graphs may also be defined for other types of incidence structure, such as the incidences between points and planes in [[Euclidean space]]. For every Levi graph, there is an equivalent [[hypergraph]], and vice versa.

== Examples ==

{{multiple image
 | align = right | perrow = 2 | total_width = 400
 | image1 = Fano plane-Levi graph.svg
 | image2 = Fano plane with nimber labels.svg
 | footer = Heawood graph and Fano plane<br><small>Vertex <span style="background-color: #eee; border: 1px solid #ddd;">3</span> is part of the circular edge <span style="background-color: #eee; border: 1px solid #ddd; white-space: nowrap;">(3, 5, 6)</span>, the diagonal edge <span style="background-color: #eee; border: 1px solid #ddd; white-space: nowrap;">(3, 7, 4)</span>, and the side edge <span style="background-color: #eee; border: 1px solid #ddd; white-space: nowrap;">(1, 3, 2)</span>.</small>
}}
* The [[Desargues graph]] is the Levi graph of the [[Desargues configuration]], composed of 10 points and  10 lines. There are 3 points on each line, and 3 lines passing through each point. The Desargues graph can also be viewed as the [[generalized Petersen graph]] G(10,3) or the [[Kneser graph|bipartite Kneser graph]] with parameters 5,2. It is 3-regular with 20 vertices.
* The [[Heawood graph]] is the Levi graph of the [[Fano plane]]. It is also known as the (3,6)-[[cage (graph theory)|cage]], and is 3-regular with 14 vertices.
* The [[Möbius–Kantor graph]] is the Levi graph of the [[Möbius–Kantor configuration]], a system of 8 points and 8 lines that cannot be realized by straight lines in the Euclidean plane. It is 3-regular with 16 vertices.
* The [[Pappus graph]] is the Levi graph of the [[Pappus configuration]], composed of 9 points and 9 lines. Like the Desargues configuration there are 3 points on each line and 3 lines passing through each point. It is 3-regular with 18 vertices.
* The [[Gray graph]] is the Levi graph of a configuration that can be realized in <math>\R^3</math> as a <math>3\times 3\times 3</math> grid of 27 points and the 27 orthogonal lines through them.
* The [[Tutte eight-cage]] is the Levi graph of the [[Cremona–Richmond configuration]]. It is also known as the (3,8)-cage, and is 3-regular with 30 vertices.
* The four-dimensional [[hypercube graph]] <math>Q_4</math> is the Levi graph of the [[Möbius configuration]] formed by the points and planes of two mutually incident tetrahedra.
* The [[Ljubljana graph]] on 112 vertices is the Levi graph of the Ljubljana configuration.<ref name="LUB">{{cite report
 | last1 = Conder | first1 = Marston |author1-link=Marston Conder
 | last2 = Malnič | first2 = Aleksander
 | last3 = Marušič | first3 = Dragan |author3-link=Dragan Marušič
 | last4 = Pisanski | first4 = Tomaž | author4-link = Tomaž Pisanski
 | last5 = Potočnik | first5 = Primož
 | publisher = University of Ljubljana Department of Mathematics
 | type = IMFM Preprint | volume = 40-845
 | title = The Ljubljana Graph
 | url = http://www.imfm.si/preprinti/PDF/00845.pdf
 | year = 2002}}.</ref>

== References ==
{{reflist}}

==External links==
*{{MathWorld|urlname=LeviGraph|title=Levi Graph}}

{{Incidence structures}}

[[Category:Families of sets]]
[[Category:Configurations (geometry)]]
[[Category:Geometric graphs]]