Line Graph in Graph Theory: Definition and Examples

Charts & pivot tables · Updated November 22, 2026

A line graph is a graph built from another graph by turning each original edge into a vertex; two new vertices are connected when their corresponding edges share an endpoint. It is written L(G) for an original graph G, and it converts questions about edges in G into questions about vertices in L(G).

What a line graph represents

In the standard definition, G is a simple, undirected graph: it has vertices and edges, with no loops or repeated edges. The vertices of L(G) stand for the edges of G, not its vertices. Two vertices in L(G) are adjacent precisely when the original edges they represent meet at a common vertex in G. The construction is also called the edge-to-vertex transformation.

For example, if G has edges uv and vw, those edges meet at v. Their corresponding vertices are therefore joined in L(G). If G also has an edge xy, with endpoints separate from u, v, and w, the vertex for xy has no connection to the vertices for uv or vw unless another original edge shares an endpoint with xy.

Vertices of G that have no incident edges do not correspond to anything in L(G), because there is no edge to turn into a new vertex. This is worth remembering when comparing the number of vertices in a graph and its line graph: the number of vertices in L(G) is the number of edges in G.

How to construct one

To draw L(G) by hand, first list every edge of G. Make one new vertex for each listed edge, and label it with that edge or a short name. Then compare every pair of original edges: join their new vertices if the pair shares an endpoint. Do not join them merely because they are close in a drawing or because their endpoints are connected by some other route.

  1. Write down the edges of G, such as ab, bc, and cd.
  2. Create one vertex in L(G) for each edge in that list.
  3. Check each pair of edges in G for a shared endpoint.
  4. Add exactly the corresponding connections in L(G), then remove any labels or crossings that are only drawing choices.

The graph’s layout on the page does not affect the result. Edges that cross in a drawing are not considered incident unless they actually share a vertex. Likewise, an edge’s two endpoints are not separate vertices in L(G); the entire edge becomes a single vertex.

A worked example

Take the path a—b—c—d. Its three edges are ab, bc, and cd, so L(G) has three vertices, which we can call x, y, and z. The edges ab and bc meet at b, and bc and cd meet at c. The outer edges ab and cd share no endpoint. Thus L(G) is the path x—y—z.

A star gives a different shape. In a star K1,3, a central vertex is joined to three outer vertices. Each of its three edges shares the central endpoint with the other two, so every pair of corresponding vertices is adjacent in the line graph. The result is a triangle, K3. More generally, the line graph of a star K1,r is the complete graph Kr.

For a triangle K3, each of its three edges meets both the others, so its line graph is also K3. These examples show that a line graph does not simply preserve a graph’s shape: its structure records which edges touch, and different original graphs can produce the same result.

Useful properties and relationships

If an edge uv in a simple graph G has endpoint degrees d(u) and d(v), its corresponding vertex in L(G) has degree d(u) + d(v) − 2. The edge uv meets d(u) − 1 other edges at u and d(v) − 1 other edges at v. The edge itself is counted in both endpoint degrees, so it is excluded from each count. In a simple graph, no other edge can meet uv at both endpoints.

Several familiar problems translate directly between G and L(G):

  • A matching in G is a set of edges with no shared endpoints. The corresponding vertices form an independent set in L(G). Consequently, the largest matching size in G equals the largest independent-set size in L(G).
  • A proper edge coloring of G assigns different colors to edges that meet. This is exactly a proper vertex coloring of L(G), so the edge-chromatic number of G equals the chromatic number of L(G).
  • A set of pairwise incident edges in G corresponds to a clique in L(G). In particular, all edges at one vertex of degree r form a clique of size r in L(G).

Line graphs are claw-free: no induced subgraph of L(G) is a three-leaf star K1,3. To see why, suppose three vertices of L(G) are all adjacent to a central vertex but not to one another. Their four corresponding edges in G would require three mutually nonincident edges each meeting the central edge. A central edge has only two endpoints, so at least two of those three edges would meet it at the same endpoint and would be adjacent to each other in L(G), a contradiction.

What happens with common graph families

Paths and cycles provide quick checks. The line graph of a path with n vertices is a path with n − 1 vertices, because each original edge becomes a vertex and only consecutive edges meet. For a cycle with n edges, each edge meets its two neighbors around the cycle, so its line graph is another cycle with n vertices. These statements assume the usual cycle has at least three vertices.

Complete graphs illustrate how dense the transformation can be. In Kn, every edge meets many others, and the line graph has n(n − 1)/2 vertices—one for each pair of original vertices. Its exact edge count depends on how many pairs of original edges share endpoints. For a star, by contrast, all original edges meet at the hub, making the line graph complete.

Isolated vertices behave differently: they disappear from the line graph, while disconnected components with edges produce separate components. If G has at least one edge and is connected, L(G) is connected, since a route through G gives a sequence of edges in which consecutive edges meet. A connected original graph consisting of a single isolated vertex has no edges, so its line graph has no vertices.

Why line graphs are useful

Line graphs are useful when the objects of interest are connections rather than locations. Suppose roads are represented by edges between intersections, and two roads conflict when they meet at an intersection. A line graph turns each road into a vertex and joins roads that conflict. A coloring of that line graph can then assign time slots or channels so that conflicting roads do not receive the same assignment.

The same model appears in scheduling and resource allocation. If each job uses a shared resource and jobs using the same resource cannot run simultaneously, represent jobs as edges incident to a resource vertex; a proper edge coloring assigns compatible time slots. The line graph makes the conflict relation explicit as ordinary vertex adjacency. Other applications include studying adjacency among links in a network and translating matching or edge-coloring questions into vertex-based problems.

The transformation is also useful in proofs and algorithms because many graph tools are stated for vertices. Turning edges into vertices can let a researcher apply an independent-set, coloring, or structural result to an edge problem. It does not automatically make every problem easier: a line graph can have many connections, and a useful solution still depends on the graph’s size and structure.

Line graph versus related graph concepts

A line graph is not the same as a planar dual. A planar dual is built from a particular planar drawing: its vertices correspond to faces, and its edges represent boundaries between faces. A line graph needs no planar embedding and uses original edges as its new vertices. A graph can have a line graph whether or not it is planar.

It is also not the complement of a graph. In a complement, the vertex set stays the same and pairs that were not adjacent become adjacent, while existing adjacencies are removed. In a line graph, the vertex set changes to represent the original edges, and adjacency is determined by incidence in the original graph.

For directed graphs, authors may define directed line graphs using a rule such as joining one directed edge to another when the first edge’s head is the second edge’s tail. This is a related but convention-dependent construction. Unless a directed version is specified, “line graph” usually refers to the standard construction for an undirected graph.

Reconstruction and limitations

Because a line graph keeps edge-incidence information, it is sometimes possible to recover the original graph from its line graph, but not always uniquely. A classic result, Whitney’s line graph theorem, says that connected simple graphs with isomorphic line graphs are themselves isomorphic, with one exceptional pair: the triangle K3 and the three-leaf star K1,3 both have line graph K3. Their line graphs alone cannot distinguish which original graph was used.

The standard definition also relies on a clear rule for when two edges count as incident. If the original structure has loops or parallel edges, conventions need to be stated because the simple-graph formulas and examples may no longer apply as written. In practical work, specify whether the input is simple, directed, or a multigraph before constructing or interpreting its line graph.

Frequently Asked Questions

What is the definition of a line graph?

For a simple undirected graph G, L(G) has one vertex for each edge of G. Two vertices in L(G) are adjacent exactly when their corresponding edges in G share an endpoint.

How many vertices does a line graph have?

L(G) has as many vertices as G has edges. Original isolated vertices contribute no vertices to L(G), because they are not endpoints of any edge.

Can two different graphs have the same line graph?

Yes. For example, K3 and K1,3 both have line graph K3. For connected simple graphs, Whitney’s theorem says this is the exceptional pair in the general reconstruction result.

Is every graph a line graph?

No. Every line graph is claw-free, so any graph containing an induced K1,3 cannot be a line graph. Being claw-free alone is not sufficient; line graphs are characterized by a more detailed set of structural restrictions.

What does a matching become in a line graph?

A matching becomes an independent set: edges in a matching do not meet, so their corresponding vertices in the line graph are not adjacent. This relationship lets edge-selection questions be expressed as vertex-selection questions.

Related

Try it: the Percentage Formula Generator: percent of, percent change, increase and decrease, with the formula.

More in Charts & pivot tables

Sources: Function behaviour and menu paths: Microsoft Support documentation for Excel. Method & sources

Spotted an error in this guide? Let us know.