Math Is Fun Forum

GemmaJ1988

Member

Registered: 2008-10-08

Posts: 39

graph theory

suppose that n=3 mod4 and we colour the edges of kn red or blue
take ri to be the no. of red edges and bi=n-1-ri to be the no. of blue egdes
show that it is not possible to have ri=bi for all i
1<=i<=n

does anyone know how i would go about answering this question.
Im unsure what the value of n would be as i dont really know what n=3 mod 4 equals. please help

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: graph theory

and we colour the edges of kn

Is "kn" the complete graph of order n?

take ri to be the no. of red edges and bi=n-1-ri to be the no. of blue egdes
show that it is not possible to have ri=bi for all i
1<=i<=n

What does it mean for i to vary?

Im unsure what the value of n would be as i dont really know what n=3 mod 4 equals.

This means when the number is divided by 4, it leaves a remainder of 3.  For example, 3 is of course equivalent to 3 mod 4, since 3/4 has remainder 3.  Similarly 7/4 is equivalent to 3 mod 4.  Continuing like this, we see this is a complete list of all integers that are equivalent to 3 mod 4:

3, 7, 11, 15, 19, 23, 27, 31, 35, ...

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

GemmaJ1988

Member

Registered: 2008-10-08

Posts: 39

Re: graph theory

yes kn is the complete graph of order n
so kn is of odd order.
but i still dont understand how to show ri is not equal to bi

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: graph theory

You have that ri is the number of red edges and bi is the number of blue edges for the graph kn.  But what does the index i mean?  It doesn't seem to have anything to do with the problem.  In other words, how would r1 and r2 be different?

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."