Line graph L(G): vertices = edges of G, adjacent iff sharing an endpoint. |V(L)|=|E(G)|. deg_L(e) = deg(u)+deg(v)-2 for edge e=uv. L(K_n) = Kneser complement. L(K_{1,n}) = K_n. Whitney (1932): L characterizes G uniquely (with few exceptions).
How to Use
Select graph:
- L(G): Line graph
- Vertices: = edges of G
- Edges: Shared endpoints
Whitney's Theorem
If L(G)≅L(H) and G,H have >4 edges, then G≅H. Exception: K_3 and K_{1,3} have the same line graph K_3. This uniqueness theorem is fundamental to graph reconstruction theory.
Properties
L(G) is always claw-free (no induced K_{1,3}). χ'(G) = χ(L(G)): edge coloring of G = vertex coloring of L(G). The line graph operation preserves many graph properties but changes the graph structure fundamentally.
Step-by-Step Instructions
- 1Select graph.
- 2Compute L(G).
- 3Count vertices/edges.
- 4Check properties.
- 5Compare to G.