Line Graph - Formal Definition

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:

    I will not let him stir
    Till I have used the approvèd means I have,
    With wholesome syrups, drugs, and holy prayers,
    To make of him a formal man again.
    William Shakespeare (1564–1616)

    ... if, as women, we accept a philosophy of history that asserts that women are by definition assimilated into the male universal, that we can understand our past through a male lens—if we are unaware that women even have a history—we live our lives similarly unanchored, drifting in response to a veering wind of myth and bias.
    Adrienne Rich (b. 1929)