cooldudeman
Badges: 17
Rep:
?
#1
Report Thread starter 4 years ago
#1
Show that any graph G with at least one edge has actually at least k\choose 2 edges, where k is the chromatic number.

My answer, please tell anything wrong with it:
0
reply
ghostwalker
  • Study Helper
Badges: 16
#2
Report 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.
Attached files
0
reply
cooldudeman
Badges: 17
Rep:
?
#3
Report Thread starter 4 years ago
#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
reply
ghostwalker
  • Study Helper
Badges: 16
#4
Report 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
reply
cooldudeman
Badges: 17
Rep:
?
#5
Report Thread starter 4 years ago
#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.

Thats a contradiction right?

Posted from TSR Mobile
0
reply
cooldudeman
Badges: 17
Rep:
?
#6
Report Thread starter 4 years ago
#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
reply
ghostwalker
  • Study Helper
Badges: 16
#7
Report 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.

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.
0
reply
cooldudeman
Badges: 17
Rep:
?
#8
Report Thread starter 4 years ago
#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
reply
ghostwalker
  • Study Helper
Badges: 16
#9
Report 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
reply
cooldudeman
Badges: 17
Rep:
?
#10
Report Thread starter 4 years ago
#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
reply
X

Quick Reply

Attached files
Write a reply...
Reply
new posts
Back
to top
Latest
My Feed

See more of what you like on
The Student Room

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

Personalise

University open days

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

Have you made up your mind on your five uni choices?

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%

Watched Threads

View All