Line graph: Difference between revisions

Revision as of 05:00, 7 July 2022

Revision as of 05:03, 7 July 2022

Line 12:

==Formal definition==

Given a graph ''{{mvar|G''}}, its line graph {{math|''L''(''G'')}} is a graph such that

* each [[vertex (graph theory)|vertex]] of {{math|''L''(''G'')}} represents an edge of ''{{mvar|G''}}; and

* two vertices of {{math|''L''(''G'')}} are [[Adjacent (graph theory)|adjacent]] if and only if their corresponding edges share a common endpoint ("are incident") in ''{{mvar|G''}}.

That is, it is the [[intersection graph]] of the edges of ''{{mvar|G''}}, representing each edge by the set of its two endpoints.<ref name="h72-71"/>

== Example ==