Formal Definition
Given a graph G, its line graph L(G) is a graph such that
- each vertex of L(G) represents an edge of G; and
- two vertices of L(G) are adjacent if and only if their corresponding edges share a common endpoint ("are adjacent") in G.
That is, it is the intersection graph of the edges of G, representing each edge by the set of its two endpoints.
Read more about this topic: Line Graph
Famous quotes containing the words formal and/or definition:
“Two clergymen disputing whether ordination would be valid without the imposition of both hands, the more formal one said, “Do you think the Holy Dove could fly down with only one wing?””
—Horace Walpole (1717–1797)
“No man, not even a doctor, ever gives any other definition of what a nurse should be than this—”devoted and obedient.” This definition would do just as well for a porter. It might even do for a horse. It would not do for a policeman.”
—Florence Nightingale (1820–1910)