What is proper edge coloring and how to show it?

Question

Show that in any proper edge coloring of K5, no color can occur more than twice. (show that four colors could not be enough for a proper edge coloring of K 5).

Could someone explain to me, with the example of a graph for example, how to do this? I don't understand what they mean with "proper edge coloring".

My own thought was: we have a complete graph with 5 vertices, so we have either 4 or 5 as the chromatic number.

Yet I need a confirmation of what I am doing and if I am doing and thinking correctly. Could someone help me with this?

I want to understand it and need an example to get it.

Answer 1

Yes, $K_5$ is always the complete graph with five vertices.

However the coloring we're talking about here is an edge coloring -- in other words, you assign a color to each edge instead of to each vertex. The coloring is "proper" if edges that share an endpoint have different colors.

For example, here is $K_4$:

O--O
|\/|
|/\|
O--O

This graph has a proper edge coloring with $3$ colors: For example color the two vertical edges red, the horizontal edges green, and the diagonals blue.

Answer 2

You want to show that in a proper edge coloring of $K_5$, no color can be assigned to $3$ or more edges.

Two edges are said to be adjacent (or incident) in $G=(V,E)$ if they have an endpoint in common and are said to be independent otherwise. Given a graph $G$, a proper edge coloring of $G$ is an assignment of colors to edges which satisfies the condition that adjacent edges are assigned different colors. This implies that in a proper edge coloring of $G$, each color class (ie the set of edges which are assigned the same color) is a set of independent edges.

Now, if a color class has $k$ edges, since no two of these $k$ edges share a common endpoint, the number of vertices incident to these $k$ edges is exactly $2k$. Thus, if a color class has size $3$, the graph must contain at least $6$ vertices. However, $K_5$ has only $5$ vertices and so cannot contain a set of $3$ independent edges. Hence, in any proper edge coloring of $K_5$, no color class has size more than $2$.