({{, (RefLink[LineGraph, paclet:ref/LineGraph])[g] 
gives the line graph of the graph g.}, {, (RefLink[LineGraph, paclet:ref/LineGraph])[{v->w,…}]
uses rules v->w to specify the graph g.}})

OpenersNotesSection(Spacer1)Details and Options

Each vertex in (RefLink[LineGraph, paclet:ref/LineGraph])[g] corresponds to an edge in g.

For an undirected graph g, two vertices in (RefLink[LineGraph, paclet:ref/LineGraph])[g] are adjacent if their corresponding edges share a common vertex.

For a directed graph g, two vertices in (RefLink[LineGraph, paclet:ref/LineGraph])[g] are adjacent if their corresponding edges are connected, i.e. the target of one edge is the source of the other edge.

The vertices in (RefLink[LineGraph, paclet:ref/LineGraph])[g] are taken to be successive integers starting at 1.

(RefLink[LineGraph, paclet:ref/LineGraph]) works with undirected graphs, directed graphs, and multigraphs.

OpenersPrimaryExamplesSection(Spacer1)Examples  (18)

OpenersExampleSection0(Spacer1)Basic Examples  (1)

The line graph of a complete graph:

LineGraph[]

OpenersExampleSection1(Spacer1)Scope  (5)

(RefLink[LineGraph, paclet:ref/LineGraph]) works with undirected graphs:

LineGraph[]

Directed graphs:

LineGraph[]

Multigraphs:

LineGraph[]

Use rules to specify the graph:

LineGraph[{1->2,1->3,2->4,3->4,3->5,4->6,5->6}]

(RefLink[LineGraph, paclet:ref/LineGraph]) works with large graphs:

g=GridGraph[{10,10,10,10}];

LineGraph[g]//EdgeCount//Timing

OpenersExampleSection3(Spacer1)Properties & Relations  (11)

The number of edges in a graph is equal to the number of vertices in its line graph:

g=PetersenGraph[5,2]

EdgeCount[g]

VertexCount[LineGraph[g]]

The line graph of a connected graph is connected:

{g = GridGraph[{3,4}],LineGraph[g]}

ConnectedGraphQ/@%

The adjacency matrix of a line graph can be computed by (m^T)m-2 I:

g=GridGraph[{2,3}]

m=IncidenceMatrix[g];

(Transpose[m].m-2 IdentityMatrix[EdgeCount[g]])//MatrixPlot

AdjacencyMatrix[LineGraph[g]]//MatrixPlot

A maximum independent set in a line graph of g corresponds to the maximum matching of g:

g=GridGraph[{2,3}]

FindIndependentVertexSet[LineGraph[g]]

FindIndependentEdgeSet[g]

A cycle graph is isomorphic to its line graph:

{g=CycleGraph[6], LineGraph[g]}

IsomorphicGraphQ@@%

The line graph of a claw (Subscript[K, 1,3]) is a triangle:

{g=CompleteGraph[{1,3}],LineGraph[g]}

The line graph of a path (Subscript[P, n]) is isomorphic to (Subscript[P, n-1]):

g=PathGraph[Range[20]]

IsomorphicGraphQ[LineGraph[g],PathGraph[Range[19]]]

The line graph of a bipartite graph is perfect:

g=CompleteGraph[{2,3}]

BipartiteGraphQ[g]

LineGraph[g]

The line graph of a Hamiltonian graph is Hamiltonian:

{g=CompleteGraph[4],LineGraph[g]}

HamiltonianGraphQ/@%

The line graph of an undirected Eulerian graph is Eulerian:

g=CompleteGraph[{2,4}]

EulerianGraphQ[g]

EulerianGraphQ[LineGraph[g]]

The line graph of an Eulerian graph is Hamiltonian:

g = CompleteGraph[5]

EulerianGraphQ[g]

HamiltonianGraphQ[LineGraph[g]]

OpenersExampleSection4(Spacer1)Neat Examples  (1)

Table[LineGraph[CompleteKaryTree[n,3]],{n,2,5}]

({{DocumentationFooterIconsRelatedFunction.png, ({{See Also}, {(RefLink[IncidenceMatrix, paclet:ref/IncidenceMatrix])  ▪  (RefLink[AdjacencyMatrix, paclet:ref/AdjacencyMatrix])  ▪  (RefLink[GraphComplement, paclet:ref/GraphComplement])}})}})

({{DocumentationFooterIconsRelatedGuide.png, ({{Related Guides}, {▪(RefLinkPlain[Graph Operations and Modifications, paclet:guide/GraphModifications])}})}})