Editing Levi graph (section)

{{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.