Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

If G is a graph containing no loops or multiple edges, then the edge-chromatic number $X_e(C)$ of G is defined to be the least number of colours needed to colour the edges of G in such a way that no two adjacent edges have the same colour.

How to find edge-chromatic number :

1)Complete Graph($K_n$)

[I know $k_n$ is (n-1)regular and if n is even then edge-chromatic number of $k_n$ is n-1 and if n is odd then edge-chromatic number of $k_n$ is n,but how to prove it??]


share|cite|improve this question
In case you're not yet aware of the practice of accepting answers, please see this faq thread. – joriki Nov 1 '12 at 9:22
Also, it seems unlikely that you don't have at least some rudimentary thoughts of your own on at least part 4) of the problem -- answers will be much more useful if you point out specifically what you already understand and what's causing you trouble. – joriki Nov 1 '12 at 9:26
up vote 3 down vote accepted

For a complete graph with an even number of vertices, this amounts to finding a 1-factorisation, such as the following:

Example (Source: David Eppstein via Wikimedia)

A general construction is formed by rotating a "starter", such as the following:

1-factorisation starter for $K_{18}$

Each rotation describes where to place the edges of a single colour. Picture source:

Mendelsohn and Rosa, One-factorizations of the complete graph—A survey, Journal of Graph Theory 9 (1985) 43–65. (link)

See also the above reference for further details on how to construct 1-factorisations of $K_{2n}$ and near 1-factorisations of $K_{2n-1}$. Hence

Observation: The edge-chromatic number of $K_{2n}$ is $2n-1$ (its maximum degree) for $n \geq 1$.

For $K_{2n-1}$, we simply start with a 1-factorisation of $K_{2n}$ and delete a vertex, which results in $2n-1$ distinct edge colours. This is the best possible, since each edge colour can occur at most $n-1$ times (without having adjacent monochromatic edges), so we need at least $$\frac{{2n-1} \choose 2}{n-1}=2n-1$$ colours.

Observation: The edge-chromatic number of $K_{2n-1}$ is $2n-1$ for $n \geq 2$.

share|cite|improve this answer

Just to add to the last part of Douglas' proof in Answer 1 ... another way to see that $K_{2n-1}$ is not ($2n-2$)-edge colorable is that if it were, then each set of monochromatic edges in the coloring would have to form a perfect matching, which is impossible in a graph with an odd number of vertices.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.