Editing Line graph (section)

===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.