# number of least edges in any graph Watch

Announcements

Page 1 of 1

Go to first unread

Skip to page:

Report

#2

(Original post by

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

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

0

reply

(Original post by

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.

**ghostwalker**)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.

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.

Does that change anything?

Posted from TSR Mobile

0

reply

Report

#4

(Original post by

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.

**cooldudeman**)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.

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?

0

reply

(Original post by

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.

**ghostwalker**)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?Thats a contradiction right?

Posted from TSR Mobile

0

reply

**ghostwalker**)

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?

Posted from TSR Mobile

0

reply

Report

#7

(Original post by

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?

**cooldudeman**)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?

0

reply

(Original post by

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.

**ghostwalker**)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.

Posted from TSR Mobile

0

reply

Report

#9

(Original post by

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

Posted from TSR Mobile

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

Posted from TSR Mobile

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.

0

reply

(Original post by

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.

**ghostwalker**)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.Thanks again.

Posted from TSR Mobile

0

reply

X

Page 1 of 1

Go to first unread

Skip to page:

### Quick Reply

Back

to top

to top