Reference articles on history, science, culture and more
Surprise meSurprise meSubscribe
Encyclopedia

Line perfect graph

Graph whose line graph is perfect

Wikipedia contributorsAdapted for Fathomly · View authors
1 min read
Source updated January 30, 2026
Image credit is listed at the end of this article.

In graph theory, a line perfect graph is a graph whose line graph is a perfect graph. Equivalently, these are the graphs in which every odd-length simple cycle is a triangle.

A graph is line perfect if and only if each of its biconnected components is a bipartite graph, the complete graph K4, or a triangular book K1,1,n. Because these three types of biconnected component are all perfect graphs themselves, every line perfect graph is itself perfect. By similar reasoning, every line perfect graph is a parity graph, a Meyniel graph, and a perfectly orderable graph.

Line perfect graphs generalize the bipartite graphs, and share with them the properties that the maximum matching and minimum vertex cover have the same size, and that the chromatic index equals the maximum degree.

Watch videos about Line perfect graphExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Line perfect graph”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Images, from Wikimedia Commons:

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.

Continue exploring

Related topics

Strangulated graph

In graph theoretic mathematics, a strangulated graph is a graph in which deleting the edges of any induced cycle of length greater than three would disconnect the remaining graph. That is, they are the graphs in which every peripheral cycle is a triangle.

Peripheral cycle

In graph theory, a peripheral cycle in an undirected graph is, intuitively, a cycle that does not separate any part of the graph from any other part. Peripheral cycles (or, as they were initially called, peripheral polygons, because Tutte called cycles "polygons") were first studied by Tutte (1963), and play important roles in the characterization of planar graphs and in generating the cycle spaces of nonplanar graphs.