Editing Line graph (section)

== Characterization and recognition ==

===Clique partition===
[[File:Line graph clique partition.svg|thumb|280px|Partition of a line graph into cliques]]
For an arbitrary graph {{mvar|G}}, and an arbitrary vertex {{mvar|v}} in {{mvar|G}}, the set of edges incident to {{mvar|v}} corresponds to a [[Clique (graph theory)|clique]] in the line graph {{math|''L''(''G'')}}. The cliques formed in this way partition the edges of {{math|''L''(''G'')}}. Each vertex of {{math|''L''(''G'')}} belongs to exactly two of them (the two cliques corresponding to the two endpoints of the corresponding edge in {{mvar|G}}).

The existence of such a partition into cliques can be used to characterize the line graphs: A graph {{mvar|L}} is the line graph of some other graph or multigraph if and only if it is possible to find a collection of cliques in {{mvar|L}} (allowing some of the cliques to be single vertices) that partition the edges of {{mvar|L}}, such that each vertex of {{mvar|L}} belongs to exactly two of the cliques.<ref name="h72-8.4">{{harvtxt|Harary|1972}}, Theorem 8.4, p.&nbsp;74, gives three equivalent characterizations of line graphs: the partition of the edges into cliques, the property of being [[Claw-free graph|claw-free]] and odd [[Diamond graph|diamond]]-free, and the nine forbidden graphs of Beineke.</ref> It is the line graph of a graph (rather than a multigraph) if this set of cliques satisfies the additional condition that no two vertices of {{mvar|L}} are both in the same two cliques. Given such a family of cliques, the underlying graph {{mvar|G}} for which {{mvar|L}} is the line graph can be recovered by making one vertex in {{mvar|G}} for each clique, and an edge in {{mvar|G}} for each vertex in {{mvar|L}} with its endpoints being the two cliques containing the vertex in {{mvar|L}}. By the strong version of Whitney's isomorphism theorem, if the underlying graph {{mvar|G}} has more than four vertices, there can be only one partition of this type.

For example, this characterization can be used to show that the following graph is not a line graph:
:[[File:LineGraphExampleA.svg|100px|class=skin-invert]]
In this example, the edges going upward, to the left, and to the right from the central degree-four vertex do not have any cliques in common. Therefore, any partition of the graph's edges into cliques would have to have at least one clique for each of these three edges, and these three cliques would all intersect in that central vertex, violating the requirement that each vertex appear in exactly two cliques. Thus, the graph shown is not a line graph.

===Forbidden subgraphs===
[[File:Forbidden line subgraphs.svg|thumb|300px|The nine minimal non-line graphs, from Beineke's forbidden-subgraph characterization of line graphs. A graph is a line graph if and only if it does not contain one of these nine graphs as an induced subgraph.]]
Another characterization of line graphs was proven in {{harvtxt|Beineke|1970}} (and reported earlier without proof by {{harvtxt|Beineke|1968}}). He showed that there are nine minimal graphs that are not line graphs, such that any graph that is not a line graph has one of these nine graphs as an [[induced subgraph]]. That is, a graph is a line graph if and only if no subset of its vertices induces one of these nine graphs. In the example above, the four topmost vertices induce a claw (that is, a [[complete bipartite graph]] {{math|''K''{{sub|1,3}}}}), shown on the top left of the illustration of forbidden subgraphs. Therefore, by Beineke's characterization, this example cannot be a line graph. For graphs with minimum degree at least 5, only the six subgraphs in the left and right columns of the figure are needed in the characterization.<ref name="mt97">{{harvtxt|Metelsky|Tyshkevich|1997}}</ref>

===Algorithms===
{{harvtxt|Roussopoulos|1973}} and {{harvtxt|Lehot|1974}} described linear time algorithms for recognizing line graphs and reconstructing their original graphs. {{harvtxt|Sysło|1982}} generalized these methods to [[directed graph]]s. {{harvtxt|Degiorgi|Simon|1995}} described an efficient data structure for maintaining a dynamic graph, subject to vertex insertions and deletions, and maintaining a representation of the input as a line graph (when it exists) in time proportional to the number of changed edges at each step.

The algorithms of {{harvtxt|Roussopoulos|1973}} and {{harvtxt|Lehot|1974}} are based on characterizations of line graphs involving odd triangles (triangles in the line graph with the property that there exists another vertex adjacent to an odd number of triangle vertices). However, the algorithm of {{harvtxt|Degiorgi|Simon|1995}} uses only Whitney's isomorphism theorem.  It is complicated by the need to recognize deletions that cause the remaining graph to become a line graph, but when specialized to the static recognition problem only insertions need to be performed, and the algorithm performs the following steps:
*Construct the input graph {{mvar|L}} by adding vertices one at a time, at each step choosing a vertex to add that is adjacent to at least one previously-added vertex. While adding vertices to {{mvar|L}}, maintain a graph {{mvar|G}} for which {{math|1=''L'' = ''L''(''G'')}}; if the algorithm ever fails to find an appropriate graph {{mvar|G}}, then the input is not a line graph and the algorithm terminates.
*When adding a vertex {{mvar|v}} to a graph {{math|''L''(''G'')}} for which {{mvar|G}} has four or fewer vertices, it might be the case that  the line graph representation is not unique. But in this case, the augmented graph is small enough that a representation of it as a line graph can be found by a [[brute force search]] in constant time.
*When adding a vertex {{mvar|v}} to a larger graph {{mvar|L}} that equals the line graph of another graph {{mvar|G}}, let {{mvar|S}} be the subgraph of {{mvar|G}} formed by the edges that correspond to the neighbors of {{mvar|v}} in {{mvar|L}}. Check that {{mvar|S}} has a [[vertex cover]] consisting of one vertex or two non-adjacent vertices. If there are two vertices in the cover, augment {{mvar|G}} by adding an edge (corresponding to {{mvar|v}}) that connects these two vertices. If there is only one vertex in the cover, then add a new vertex to {{mvar|G}}, adjacent to this vertex.
Each step either takes constant time, or involves finding a vertex cover of constant size within a graph {{mvar|S}} whose size is proportional to the number of neighbors of {{mvar|v}}. Thus, the total time for the whole algorithm is proportional to the sum of the numbers of neighbors of all vertices, which (by the [[handshaking lemma]]) is proportional to the number of input edges.