Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[ILikePie]

Aye, thanks. n = 2, 3, am I right? My book says it's 2 but not 3 for some reason.

[Vector]

n = 2, -3.  It isn't -3 because you know n is even.

[KaminaSquirtle]

Necro post!
I feel like I'm hitting my head against a wall on this problem, so if anyone could give me a nudge in the right direction that would be great:

Show that a graph G has at least (χ(G) choose 2) edges.  (χ(G) is the chromatic number of G)

It seems like a really simple problem, so I must be missing something obvious.

[Sowelu]

I have no experience in this field but let me take a stab.  Or at least help others take a stab.

First let me make sure I've still got the terminology right...
Chromatic number = if you give every node in the graph a color, the chromatic number is the minimum number of colors required to make sure that no two nodes connected by an edge have the same color, right?
N choose k = The number of unique subsets of N that contain exactly k elements, right?  So 4 choose 2 means, if you have four apples, the number of different pairs of apples you could pick from them.  Specifically, it's equal to n!/(k!(n-k)!).

Okay.  Smallest graph = 1 node = 1 color, 0 edges.
Add another node, and another edge, 2 nodes, 2 colors, 1 edge.
Add another node, plus one edge to each of those colors. 3 nodes, 3 colors, 3 edges.
Again... 4 nodes, 4 colors, 7 edges.
Every time you increase the chromatic number in a way that requires the least additional edges, you add one node, and n edges where n is the number of previously-existing nodes.  (Each new node needs an edge to every existing node, otherwise it would be able to duplicate a color of a node it was not connected to).  Or, put more concisely, when the chromatic number is X, you have X edges and (2^(X-1))-1 edges.

Bluh bluh dumb at math

[KaminaSquirtle]

Thanks, that's really clever, first showing that complete graphs have the least edges per chromatic number (trivial), and then showing that the complete graphs will always have at least (χ(K_n) choose 2) edges, where K_n is the complete graph with n nodes.

I should be able to go from there.  The only mistake you made with the terminology is that (n choose k) = n!/(k!(n-k)!), not n!/k!, but that shouldn't interfere with the problem.

Lemme try and finish this one up.

Edit: I think you messed up somewhere, since K₄ only has 6 edges, and the general formula for number of edges of a complete graph is n(n-1)/2, where n is the number of nodes, which equals the number of colors in this case.  If we evaluate n!/(k!(n-k)!) where k=2, we get exactly n(n-1)/2.  So the proof is done.

Derp.  I was missing something obvious.

[Sowelu]

Oh!  Whoops.  Let me edit that post so I don't confuse other people.  Oh well.    I never did finish that math minor...

[KaminaSquirtle]

Ahhhhh, we keep editing while the other posts!
Anyway, solved.

[Sowelu]

No more edits for me.  Yay!

[Urist is dead tome]

Someone tell me about quadratic equations please.

[Leafsnail]

What?  You mean like... how to solve them, or something deeper than that?

[Darvi]

Quadratic equations follow  the formula a*x^2 + b*x+c ,where a,b, and c can be any real constants (or imaginary, but that's neither here nor there).

They can either have 2 real solutions (or roots), one unique solution, or no real solution at all.

The amount of solutions depends on the discriminant

If it's positive, you have 2 roots, is it negative, there is no real root (but 2 imaginary ones), and if delta is 0 then you have one root.

The roots then can be calculated with the following formulae:

and

if the discriminant is positive or

if it's zero.

Derivative is 2a*x +b and indefinite integrals are a/3*x^3+b/2*x^2+c*x + constant




Is that enough?^^

[Urist is dead tome]

Thanks Darvi, I really appreciate the help.

[Sowelu]

Although your custom smiley links are broken

[Darvi]

What smileys? Those are formulas that I got from wikipedia.

[Sowelu]

I meant these at the end:

Code: [Select]

[img]http://www.bay12forums.com/smf/file:///C:/Users/Willy/AppData/Local/Temp/moz-screenshot-3.png[/img]