# number of least edges in any graphWatch

Announcements
#1
Show that any graph G with at least one edge has actually at least edges, where is the chromatic number.

0
4 years ago
#2
(Original post by cooldudeman)
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.
0
#3
(Original post by 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.
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.

Does that change anything?

Posted from TSR Mobile
0
4 years ago
#4
(Original post by 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.
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.

Like between two colour classes, there would be at least one edge.
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?
0
#5
(Original post by 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?
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.

Posted from TSR Mobile
0
#6
(Original post by 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?
Here is my polished answer. Please have a look at it now.

Posted from TSR Mobile
0
4 years ago
#7
(Original post by 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.

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.
0
#8
(Original post by 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.
I've tried explaining this point a lot better in the new answer I posted (two posts up). Would that be ok do you think?

Posted from TSR Mobile
0
4 years ago
#9
(Original post by cooldudeman)
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.
0
#10
(Original post by 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.
Yes I understand. Thanks I'll change that.

Thanks again.

Posted from TSR Mobile
0
X

new posts
Back
to top
Latest
My Feed

### Oops, nobody has postedin the last few hours.

Why not re-start the conversation?

see more

### See more of what you like onThe Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

### University open days

• University of East Anglia
Sun, 20 Oct '19
• University for the Creative Arts
Sun, 20 Oct '19
• University of Gloucestershire
Sun, 20 Oct '19

### Poll

Join the discussion

Yes I know where I'm applying (86)
67.72%
No I haven't decided yet (25)
19.69%
Yes but I might change my mind (16)
12.6%