number of least edges in any graph

If we choose vertices from different colour classes, it will make an edge.

I don't have a complete answer, however the quoted line is not true - consider the attached graph on 6 vertices, with k=3. Vertices a,b are different colours, but there is no edge between them.

Sorry it was actually meant to say:
If we choose TWO vertices from different colour classes, it will make an edge.

But I dont think that makes a difference to what you are saying does it.

I didn't really mean that there HAS to be an edge, just saying there would be an edge if chosen.

Like between two colour classes, there would be at least one edge.

If you choose an edge it would have to exist. But you need to show that there is an edge in the first place, before you can choose it.



This is the key to the whole question. Is there at least one edge between any two colour classes? That's what you need to show - unless you're able to assume that for some reason.

I would start by assuming that there are two colour classes where there is no edge between the vertices of one class and the other, and show that this gives a contradiction.

Edit: Also, on a separate point, you may wish to consider why your original graph must have at least one edge. What if it has no edges? What's k then?

If you choose an edge it would have to exist. But you need to show that there is an edge in the first place, before you can choose it.



This is the key to the whole question. Is there at least one edge between any two colour classes? That's what you need to show - unless you're able to assume that for some reason.

I would start by assuming that there are two colour classes where there is no edge between the vertices of one class and the other, and show that this gives a contradiction.

Edit: Also, on a separate point, you may wish to consider why your original graph must have at least one edge. What if it has no edges? What's k then?

Ok it must have at least one edge from different colour classes otherwise the chriomatic number k can be smaller than it already is which is impossible.

Thats a contradiction right?

True, but I would expect a bit more detail with a few symbols. There's no justification there; you've not said how it is that it can be made smaller.

Here is my polished answer. Please have a look at it now.

Posted from TSR Mobile

Looks good: A couple of comments.


When talking about the subsets of G, it would be better, IMO, to say we can partition V (the vertex set) based on the assigned colours. Since G has at least one edge, then there are at least 2 colour classes.

For "join these two into one colour class", I would say something like.

If two colour classes, with colours a,b say, have no connecting edge, then we can relabel all vertices with colour b, to have colour a, and produce a vertex colouring with k-1 colours, contradicting the definition of the chromatic number.

Note: My terminology may not be exact.