Line graph: Difference between revisions

Revision as of 14:10, 13 February 2023

Revision as of 22:50, 19 February 2023

Line 34:

Thus,

* The line graph of a [[connected graph]] is connected. If {{mvar|G}} is connected, it contains a [[path (graph theory)|path]] connecting any two of its edgesvertices, which translates into a path in {{math|''L''(''G'')}} containing any two of the verticesedges of {{math|''L''(''G'')}}. However, a graph {{mvar|G}} that has some isolated vertices, and is therefore disconnected, may nevertheless have a connected line graph.<ref>The need to consider isolated vertices when considering the connectivity of line graphs is pointed out by {{harvtxt|Cvetković|Rowlinson|Simić|2004}}, [https://books.google.com/books?id=FA8SObZcbs4C&pg=PA32 p.&nbsp;32].</ref>

* A line graph has an [[articulation point]] if and only if the underlying graph has a [[bridge (graph theory)|bridge]] for which neither endpoint has degree one.<ref name="h72-71"/>

* For a graph {{mvar|G}} with {{mvar|n}} vertices and {{mvar|m}} edges, the number of vertices of the line graph {{math|''L''(''G'')}} is {{mvar|m}}, and the number of edges of {{math|''L''(''G'')}} is half the sum of the squares of the [[degree (graph theory)|degrees]] of the vertices in {{mvar|G}}, minus {{mvar|m}}.<ref>{{harvtxt|Harary|1972}}, Theorem 8.1, p.&nbsp;72.</ref>