From Edges to Vertices
In a proper edge coloring, edges that meet at a vertex must receive different colors. This is a constraint on pairs of edges. A line graph converts those pairs into ordinary adjacency: it represents each original edge by a vertex and joins two such vertices exactly when the original edges meet. The result lets us treat an edge-coloring question as a vertex-coloring question without changing which pairs must receive different colors.
Throughout, \(G=(V,E)\) is a finite simple graph: it has no loops or multiple edges. Two distinct edges are incident if they share an endpoint. A proper edge coloring assigns colors to edges so that incident edges have different colors. A proper vertex coloring assigns colors to vertices so that adjacent vertices have different colors. A matching is a set of pairwise nonincident edges; thus, each color class in a proper edge coloring is a matching.
When constructing \(L(G)\), keep the original edges as identifiable labels for the new vertices. Then consider each pair of distinct original edges once: include an edge in \(L(G)\) if and only if the pair shares an endpoint. Original vertices are not themselves copied into the line graph. In particular, an isolated vertex of \(G\) creates no vertex in \(L(G)\).
The Coloring Correspondence
Proof. Fix a set \(C\) of \(k\) colors. Given a proper edge coloring \(c:E(G)\to C\), define a vertex coloring \(\widehat c:V(L(G))\to C\) by \(\widehat c(e)=c(e)\) for each \(e\in E(G)\). If vertices \(e,f\) of \(L(G)\) are adjacent, then \(e\) and \(f\) share an endpoint in \(G\). Since \(c\) is a proper edge coloring, \(c(e)\ne c(f)\). Hence \(\widehat c\) is a proper vertex coloring.
Conversely, given a proper vertex coloring \(q:V(L(G))\to C\), define an edge coloring of \(G\) by \(c(e)=q(e)\) for every \(e\in E(G)=V(L(G))\). If two edges of \(G\) share an endpoint, their corresponding vertices in \(L(G)\) are adjacent. Properness of \(q\) therefore gives them different colors, so \(c\) is a proper edge coloring. These two transformations leave the color assigned to each edge label unchanged; applying one after the other recovers the original coloring. They are inverse bijections. If \(E(G)=\varnothing\), both graphs have no objects to color, so the stated minimum is \(0\) on both sides. Otherwise the same bijection for every palette shows that the two minimum numbers of colors are equal. \(\square\)
The correspondence preserves not just the minimum number of colors but every assignment from a fixed palette: each edge color in \(G\) becomes the color of its corresponding vertex in \(L(G)\), and vice versa. The theorem does not say that \(G\) and \(L(G)\) are the same graph; they generally have different vertex sets and different structures. It says that their coloring constraints match exactly.
Constructing Line Graphs in Examples
Worked Example: A Triangle with a Pendant Edge
Let \(G\) have vertex set \(V(G)=\{1,2,3,4\}\) and edge set \(E(G)=\{12,23,31,34\}\). Write \(e_{12},e_{23},e_{31},e_{34}\) for the four vertices of \(L(G)\). Test every pair of original edges once:
| Pair of original edges | Shared endpoint? | Edge in \(L(G)\)? |
|---|---|---|
| \(12,23\) | Yes, vertex \(2\) | \(e_{12}e_{23}\) |
| \(12,31\) | Yes, vertex \(1\) | \(e_{12}e_{31}\) |
| \(12,34\) | No | No |
| \(23,31\) | Yes, vertex \(3\) | \(e_{23}e_{31}\) |
| \(23,34\) | Yes, vertex \(3\) | \(e_{23}e_{34}\) |
| \(31,34\) | Yes, vertex \(3\) | \(e_{31}e_{34}\) |
Therefore \(V(L(G))=\{e_{12},e_{23},e_{31},e_{34}\}\) and \(E(L(G))=\{e_{12}e_{23},e_{12}e_{31},e_{23}e_{31},e_{23}e_{34},e_{31}e_{34}\}\). As a check, the four degrees in \(L(G)\), in the displayed vertex order, are \(2,3,3,2\), whose sum is \(2+3+3+2=10\). Each edge contributes \(1\) to the degree of each of its two endpoints, so this degree sum gives \(10/2=5\) edges, matching the five listed.
For a coloring, assign colors red, blue, green, red to \(e_{12},e_{23},e_{31},e_{34}\), respectively. The listed adjacencies have unequal colors: the triangle on \(e_{12},e_{23},e_{31}\) has three different colors, and \(e_{34}\) is adjacent only to \(e_{23}\) and \(e_{31}\), not to red-colored \(e_{12}\). The corresponding edge coloring of \(G\) gives \(12\) red, \(23\) blue, \(31\) green, and \(34\) red. Checking in \(G\), the edges meeting at \(1\) have colors red and green, those meeting at \(2\) have red and blue, and those meeting at \(3\) have blue, green, and red. The edge \(34\) can reuse red because it is disjoint from \(12\).
Worked Example: Three Edges at One Vertex
Let \(G\) have \(V(G)=\{0,1,2,3\}\) and \(E(G)=\{01,02,03\}\). Denote the corresponding line-graph vertices by \(e_{01},e_{02},e_{03}\). Each pair of distinct edges shares vertex \(0\), so the pair checks are:
| Pair | Shared endpoint | Line-graph edge |
|---|---|---|
| \(01,02\) | \(0\) | \(e_{01}e_{02}\) |
| \(01,03\) | \(0\) | \(e_{01}e_{03}\) |
| \(02,03\) | \(0\) | \(e_{02}e_{03}\) |
Thus \(L(G)\) has three vertices and all three possible edges between them. The independent pair count also gives \(\binom{3}{2}=3\) pairs, all of which share \(0\), confirming that no pair was missed. Assign red to \(01\), blue to \(02\), and green to \(03\). The corresponding vertices of \(L(G)\) are pairwise adjacent and have distinct colors. Two colors cannot suffice: all three edges of \(G\) meet at \(0\), so any proper edge coloring must assign three distinct colors. This agrees with the line graph, where its three pairwise adjacent vertices also require three distinct colors.
Worked Example: Disjoint Edges and an Isolated Vertex
Let \(G\) have \(V(G)=\{1,2,3,4,5\}\) and \(E(G)=\{12,34\}\). Vertex \(5\) is isolated. The line graph has \(V(L(G))=\{e_{12},e_{34}\}\). There is one pair of distinct original edges to test: \(12\) and \(34\). They share no endpoint, so \(E(L(G))=\varnothing\). The isolated vertex \(5\) contributes nothing to the line graph because it is not an edge.
Both vertices of \(L(G)\) can receive the same color, just as the two disjoint edges of \(G\) can receive the same color. For a palette of \(k\) colors, where \(k\ge1\), each of the two objects can be assigned any palette color independently: there are \(k\cdot k=k^2\) assignments on either side. The bijection sends each assignment to the same pair of colors on \(12\) and \(34\). This example also shows why the line graph need not be connected even when one is considering a single original graph: its vertices correspond to edges, and adjacency records only whether those edges meet.
A Useful Degree Check
Proof. The neighbors of the vertex \(uv\) in \(L(G)\) are exactly the other edges incident with \(u\) or \(v\). There are \(\deg_G(u)-1\) edges incident with \(u\) other than \(uv\), and \(\deg_G(v)-1\) edges incident with \(v\) other than \(uv\). These two collections are disjoint: an edge in both would have endpoints \(u\) and \(v\), and in a simple graph the only such edge is \(uv\), which was excluded. Adding their sizes gives \((\deg_G(u)-1)+(\deg_G(v)-1)=\deg_G(u)+\deg_G(v)-2\), as required. \(\square\)
For the first example, \(\deg_G(1)=2\), \(\deg_G(2)=2\), \(\deg_G(3)=3\), and \(\deg_G(4)=1\). The proposition gives line-graph degrees \(2+2-2=2\) for \(12\), \(2+3-2=3\) for \(23\), \(3+2-2=3\) for \(31\), and \(3+1-2=2\) for \(34\). These are the degrees obtained by counting the neighbors in the constructed edge list. The formula is a check on the construction, not a replacement for identifying which edges of \(L(G)\) are present.
Common Pitfall: Confusing Incidence with Adjacency
A common error is to include an edge in \(L(G)\) merely because two original edges occur in the same graph or are connected by a path. For example, in the first worked example, \(12\) and \(34\) are both edges of \(G\), but they have no common endpoint. A wrong construction might therefore list \(e_{12}e_{34}\) as an edge of \(L(G)\). The correction is to test endpoints: \(12\) has endpoints \(1,2\), while \(34\) has endpoints \(3,4\), and the sets \(\{1,2\}\) and \(\{3,4\}\) are disjoint. Thus \(e_{12}e_{34}\notin E(L(G))\). In the coloring above, both corresponding vertices may therefore be red.
Conversely, edges that share an endpoint must be adjacent in the line graph even if they do not lie on a cycle. In the same example, \(23\) and \(34\) are adjacent in \(L(G)\) because both contain endpoint \(3\). Consequently they cannot both receive the same color in a proper edge coloring. The defining test is exactly “share an endpoint,” not “belong to the same component,” “lie on a common cycle,” or “are consecutive in a chosen drawing.”
The line-graph translation is useful whenever the question concerns which original edges may share a color. It allows vertex-coloring language and tools to be applied to those constraints, while the correspondence guarantees that a coloring found on one side translates back without alteration. When constructing \(L(G)\), label its vertices by the original edges and check every pair once; when checking a proposed coloring, verify adjacency in \(L(G)\), or equivalently verify incidence in \(G\).
Check Your Understanding
Use the definition of the line graph and the coloring correspondence to answer the following.
- Let \(G\) have \(V(G)=\{1,2,3\}\) and \(E(G)=\{12,23\}\). Give the vertex and edge sets of \(L(G)\).
- For a graph with \(E(G)=\varnothing\), what are the vertex and edge sets of \(L(G)\), and what values do the stated conventions give for \(\chi'(G)\) and \(\chi(L(G))\)?
- Suppose two distinct edges of \(G\) share an endpoint. Explain why their corresponding vertices must have different colors in every proper vertex coloring of \(L(G)\).
- In a simple graph, an edge \(uv\) has endpoint degrees \(4\) and \(2\). Use the degree proposition to find the degree of its vertex in \(L(G)\), and state the two sets of incident edges being counted.
- Give a concrete reason that two edges in the same connected component of \(G\) need not be adjacent in \(L(G)\).