2
$\begingroup$

Problem solution

So i have this solution for proving that the chromatic index of graph G, that is drawn on the image, equals 5.

I understand everything until that point, where i put "$?$" in circle. I don't know what that means, also the solution was orginally in a different language, so perhaps "$color$ $class$" isn't the right name for it, i used direct translation from slovene into english. Also that lemma means that $2m$ (where m is the number of edges) is equal to a product of number of vertices and number of edges in a single vertice, because the number of edges to every vertice is the same(4). If anyone can help me understand how we got to that inclusion, where i have a question mark, it would be great. Thank you in advance.

$\endgroup$
2
$\begingroup$

The proof is by contradiction. It assumes the graph can be edge colored using four colors. If each color class had at most four edges, then all the color classes together would contain at most $4\cdot4=16$ edges. But the graph has $18$ edges, so at least one color class must have at least five edges in it.

Now the five same-colored edges must never be incident on the same vertex. So the ten endpoints of those five edges are distinct vertices. That is the contradiction, since the graph has only nine vertices.

$\endgroup$
0
$\begingroup$

I think they mean there exists a color such that the number of edges of that color is at least $5$. Notice it's first assumed the chromatic index is $4$ so if each color had only $4$ or less edges of that color, you'd have at most $16$ edges, a contradiction since you have $18$ edges.

Since there exists $5$ edges of a single color, and since none of these edges share a vertex, then there are $10$ vertices associated with these edges, a contradiction since there are $9$ vertices. Thus, the chromatic index is at least $5$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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