Levi graph

Levi graph or incidence graph is a bipartite graph associated with an incidence structure.

Any geometric incidence structure of points and lines in Euclidean plane such as Desargues configuration gives rise to a (combinatorial) incidence structure.

Example: Desargues Configuration

Desargues configuration is composed of

• 10 points (red dots) and
• 10 lines
• There are 3 points on each line.
• There are 3 lines passing through each point.

The corresponding Levi graph is the generalized Petersen graph G(10,3), also known as the Desargues graph.

Example: Pappus Configuration

Pappus configuration is composed of

• 9 points and
• 9 lines
• There are 3 points on each line.
• There are 3 lines passing through each point.

See also

• Desargues' theorem
• Pappus's hexagon theorem