Let \(G\) be a finite simple graph, and let \(L(G)\) denote its line graph — the graph whose vertices are the edges of \(G\), with two such vertices adjacent exactly when the corresponding edges of \(G\) share an endpoint. Then the maximum degree \(\Delta (G)\) of \(G\) is at most the chromatic number of \(L(G)\); that is, writing \(\chi '(G) = \chi (L(G))\) for the edge chromatic number of \(G\), one has

Let \(G\) be a finite loopless graph, and let \(\mathscr {C}\) be a \(k\)-edge colouring of \(G\), that is, an arbitrary assignment of one of the colours \(1, 2, \ldots , k\) to each edge (not necessarily proper). For a vertex \(v\), write \(c(v)\) for the number of distinct colours represented at \(v\), and \(d(v)\) for its degree. Then

Let \(G\) be a finite graph and let \(C\) be a \(k\)-edge colouring of \(G\), that is, an assignment of one of the colours \(1, 2, \ldots , k\) to each edge. Then \(C\) is proper — no two distinct edges that share a common endpoint receive the same colour — if and only if \(c(v) = d(v)\) for every vertex \(v\), where \(c(v)\) is the number of distinct colours represented at \(v\) and \(d(v)\) is the degree of \(v\).

Let \(G\) be a finite connected simple graph that is not an odd cycle (that is, \(G\) is not a single cycle of odd length using every edge of \(G\)). Then the edges of \(G\) can be assigned two colours in such a way that at every vertex \(v\) of degree at least \(2\), both colours are represented at \(v\) — each of the two colours appears on some edge incident with \(v\).

Let \(\mathscr {C}\) be an optimal \(k\)-edge colouring of a finite graph \(G\), and suppose there is a vertex \(u\) and colours \(i, j\) for which colour \(i\) is not represented at \(u\) while at least two edges incident with \(u\) carry colour \(j\). Then the connected component of \(u\) in the subgraph \(G[E_i \cup E_j]\) spanned by the edges coloured \(i\) or \(j\) is an odd cycle: there is a closed walk based at \(u\) that is a cycle of odd length whose vertices are precisely those of that component.

Let \(G\) be a bipartite simple graph on a finite vertex set, and let \(\Delta (G)\) denote its maximum degree. Then the chromatic number of the line graph of \(G\) — equivalently, the least number of colours needed to colour the edges of \(G\) so that no two edges sharing an endpoint receive the same colour — equals \(\Delta (G)\).

Let \(G\) be a simple graph on a finite vertex set, with maximum degree \(\Delta (G)\), and let \(\chi '(G)\) denote its chromatic index — that is, the chromatic number of the line graph of \(G\), equivalently the least number of colours needed to colour the edges of \(G\) so that any two edges sharing an endpoint receive distinct colours. Then either \(\chi '(G) = \Delta (G)\) or \(\chi '(G) = \Delta (G) + 1\).

Let \(G\) be a finite simple graph with maximum degree \(\Delta (G)\), and let \(L(G)\) denote its line graph. Then the chromatic number of \(L(G)\) — equivalently, the chromatic index (edge chromatic number) \(\chi '(G)\) of \(G\) — satisfies

Let \(G\) be a finite simple graph, and let \(M\) and \(N\) be two disjoint matchings of \(G\) (each a set of edges, no two of which share a vertex) with \(\left\lvert N\right\rvert \lt \left\lvert M\right\rvert \). Then there exist disjoint matchings \(M'\) and \(N'\) of \(G\) such that \(\left\lvert M'\right\rvert = \left\lvert M\right\rvert - 1\), \(\left\lvert N'\right\rvert = \left\lvert N\right\rvert + 1\), and \(M' \cup N' = M \cup N\).

Let \(G\) be a finite bipartite graph with edge set \(E\) of size \(\varepsilon = |E|\) and maximum degree \(\Delta \), and let \(p\) be a positive integer with \(\Delta \le p\). Then there exist \(p\) matchings \(M_1, M_2, \ldots , M_p\) of \(G\) that are pairwise edge-disjoint and satisfy

with each of their sizes controlled by

in particular, any two of the matchings differ in size by at most one.

Let \(G\) be a finite bipartite simple graph, and let \(\Delta \) denote its maximum degree. Then there is a finite bipartite simple graph \(H\) that is \(\Delta \)-regular (every vertex of \(H\) has degree exactly \(\Delta \)) together with an embedding of \(G\) into \(H\) — an injection \(V(G) \to V(H)\) under which two vertices of \(G\) are adjacent if and only if their images are adjacent in \(H\). In other words, every finite bipartite graph is (isomorphic to) an induced subgraph of a bipartite graph regular of degree equal to \(\Delta \).

Let \(G\) be a finite bipartite simple graph with minimum degree \(\delta \gt 0\). Then there is an edge colouring \(C\) of \(G\) using \(\delta \) colours — that is, a function assigning to each edge one of the colours \(1, 2, \ldots , \delta \), not required to be proper — such that every colour is represented at every vertex: for each vertex \(v\) and each colour \(i\), some edge incident with \(v\) is assigned colour \(i\).

For every integer \(n \ge 1\), the complete graph \(K_{2n-1}\) on \(2n-1\) vertices has edge-chromatic number equal to \(2n-1\); that is, its edges can be properly coloured with \(2n-1\) colours but no fewer. Equivalently, the chromatic number of the line graph of \(K_{2n-1}\) is \(2n-1\).

For every integer \(n \ge 1\), the complete graph \(K_{2n}\) on \(2n\) vertices has edge chromatic number \(\chi '(K_{2n}) = 2n - 1\); equivalently, the chromatic number of the line graph of \(K_{2n}\) equals \(2n - 1\).

Let \(G\) be a finite simple graph whose number of vertices is odd, and suppose \(G\) is \(k\)-regular for some integer \(k \ge 1\) (every vertex has exactly \(k\) neighbours). Then the edge chromatic number of \(G\) — equivalently, the chromatic number of its line graph — equals \(\Delta (G) + 1\), where \(\Delta (G)\) is the maximum degree of \(G\). Writing \(\chi '(G)\) for the edge chromatic number,

Let \(G\) be a finite simple graph whose vertex set has \(2n+1\) elements for some \(n \in \mathbb {N}\), and write \(\Delta \) for its maximum degree and \(\varepsilon \) for its number of edges. If \(\varepsilon \gt n\Delta \), then the edge chromatic number of \(G\) equals \(\Delta + 1\); that is, the least number of colours needed to colour the edges of \(G\) so that no two edges sharing an endpoint receive the same colour is exactly \(\Delta + 1\).

Let \(G\) be a \(k\)-regular simple graph, with \(k \ge 2\), on a finite vertex set whose cardinality is even, and let \(uv\) be an edge of \(G\). Form the graph \(G'\) by subdividing the edge \(uv\): delete it and join its ends \(u\) and \(v\) by a path of length two through a single new vertex. Then the chromatic number of the line graph of \(G'\) — equivalently, the edge chromatic number \(\chi '(G')\) — equals \(\Delta (G') + 1\), where \(\Delta (G')\) is the maximum degree of \(G'\).

Let \(G\) be a finite simple \(k\)-regular graph with \(k \ge 1\) whose vertex set has odd cardinality, and let \(F\) be a set of edges of \(G\) satisfying \(2\left\lvert F\right\rvert \lt k\) (that is, fewer than \(k/2\) edges). Write \(G - F\) for the graph obtained from \(G\) by deleting the edges in \(F\), and let \(\Delta \) denote its maximum degree. Then the chromatic index of \(G - F\)—equivalently, the chromatic number of its line graph—equals \(\Delta + 1\). (Beineke and Wilson.)

Let \(G\) be a finite simple graph that is \(3\)-regular and admits a proper \(3\)-edge-colouring. If \(G\) is uniquely \(3\)-edge-colourable — meaning any two proper \(3\)-edge-colourings of \(G\) agree up to a permutation of the three colours — then \(G\) contains a Hamiltonian cycle, that is, a closed walk that visits every vertex exactly once.

Let \(G\) be a finite simple graph, let \(K_2\) denote the complete graph on two vertices, and form the Cartesian product \(G \square K_2\) — the prism over \(G\), whose vertices are the pairs \((v,i)\) with \(v\) a vertex of \(G\) and \(i \in \{ 0,1\} \), and in which \((v,i)\) is adjacent to \((v',i')\) exactly when either \(v = v'\) and \(i \neq i'\), or \(i = i'\) and \(v,v'\) are adjacent in \(G\). Then the edge chromatic number of \(G \square K_2\) — that is, the chromatic number of its line graph — equals its maximum degree \(\Delta (G \square K_2)\).

Let \(G\) and \(H\) be finite simple graphs, and let \(G \square H\) denote their Cartesian product, the graph on \(V(G) \times V(H)\) in which \((u,x)\) and \((v,y)\) are adjacent exactly when either \(u = v\) and \(x \sim y\) in \(H\), or \(x = y\) and \(u \sim v\) in \(G\). For a graph \(K\), write \(\Delta (K)\) for its maximum degree and \(\chi '(K)\) for its chromatic index, the least number of colors needed to color the edges of \(K\) so that any two edges meeting at a common vertex receive different colors (equivalently, the chromatic number of the line graph of \(K\)). If \(H\) has at least one edge, so that \(\Delta (H) \gt 0\), and \(H\) satisfies \(\chi '(H) = \Delta (H)\), then \(\chi '(G \square H) = \Delta (G \square H)\).