Editing Line graph (section)

===Translated properties of the underlying graph===
Properties of a graph {{mvar|G}} that depend only on adjacency between edges may be translated into equivalent properties in {{math|''L''(''G'')}} that depend on adjacency between vertices. For instance, a [[Matching (graph theory)|matching]] in {{mvar|G}} is a set of edges no two of which are adjacent, and corresponds to a set of vertices in {{math|''L''(''G'')}} no two of which are adjacent, that is, an [[Independent set (graph theory)|independent set]].<ref name="paschos">{{citation|title=Combinatorial Optimization and Theoretical Computer Science: Interfaces and Perspectives|first=Vangelis Th.|last=Paschos|publisher=John Wiley & Sons|year=2010|isbn=9780470393673|page=394|url=https://books.google.com/books?id=bOMH9fPOicgC&pg=PA394|quotation=Clearly, there is a one-to-one correspondence between the matchings of a graph and the independent sets of its line graph.}}</ref>

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 edges, which translates into a path in {{math|''L''(''G'')}} containing any two of the vertices 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>
* An [[Independent set (graph theory)|independent set]]  in {{math|''L''(''G'')}} corresponds to a [[Matching (graph theory)|matching]] in {{mvar|G}}. In particular, a [[maximum independent set problem|maximum independent set]] in {{math|''L''(''G'')}} corresponds to [[maximum matching]] in {{mvar|G}}. Since maximum matchings may be found in polynomial time, so may the maximum independent sets of line graphs, despite the hardness of the maximum independent set problem for more general families of graphs.<ref name="paschos"/> Similarly, a [[rainbow-independent set]] in {{math|''L''(''G'')}} corresponds to a [[rainbow matching]] in {{mvar|G}}.
* The [[edge chromatic number]] of a graph {{mvar|G}} is equal to the [[vertex chromatic number]] of its line graph {{math|''L''(''G'')}}.<ref>{{citation|title=Graph Theory|volume=173|series=Graduate Texts in Mathematics|first=Reinhard|last=Diestel|publisher=Springer|year=2006|isbn=9783540261834|page=112|url=https://books.google.com/books?id=aR2TMYQr2CMC&pg=PA112}}. Also in [http://diestel-graph-theory.com/basic.html free online edition], Chapter 5 ("Colouring"), p.&nbsp;118.</ref>
* The line graph of an [[edge-transitive graph]] is [[vertex-transitive graph|vertex-transitive]]. This property can be used to generate families of graphs that (like the [[Petersen graph]]) are vertex-transitive but are not [[Cayley graph]]s: if {{mvar|G}} is an edge-transitive graph that has at least five vertices, is not bipartite, and has odd vertex degrees, then {{math|''L''(''G'')}} is a vertex-transitive non-Cayley graph.<ref>{{citation
 | last1 = Lauri | first1 = Josef
 | last2 = Scapellato | first2 = Raffaele
 | isbn = 0-521-82151-7
 | location = Cambridge
 | mr = 1971819
 | page = 44
 | publisher = Cambridge University Press
 | series = London Mathematical Society Student Texts
 | title = Topics in graph automorphisms and reconstruction
 | url = https://books.google.com/books?id=hsymFm0E0uIC&pg=PA44
 | volume = 54
 | year = 2003}}. Lauri and Scapellato credit this result to Mark Watkins.</ref>
* If a graph {{mvar|G}} has an [[Euler cycle]], that is, if {{mvar|G}} is connected and has an even number of edges at each vertex, then the line graph of {{mvar|G}} is [[Hamiltonian graph|Hamiltonian]]. However, not all Hamiltonian cycles in line graphs come from Euler cycles in this way; for instance, the line graph of a Hamiltonian graph {{mvar|G}} is itself Hamiltonian, regardless of whether {{mvar|G}} is also Eulerian.<ref>{{harvtxt|Harary|1972}}, Theorem 8.8, p.&nbsp;80.</ref>
* If two simple graphs are [[graph isomorphism|isomorphic]] then their line graphs are also isomorphic. The [[Line graph#Whitney isomorphism theorem|Whitney graph isomorphism theorem]] provides a converse to this for all but one pair of connected graphs.
* In the context of complex network theory, the line graph of a random network preserves many of the properties of the network such as the [[Small-world network|small-world property]] (the existence of short paths between all pairs of vertices) and the shape of its [[degree distribution]].{{sfnp|Ramezanpour|Karimipour|Mashaghi|2003}} {{harvtxt|Evans|Lambiotte|2009}} observe that any method for finding vertex clusters in a complex network can be applied to the line graph and used to cluster its edges instead.