0
$\begingroup$

Prove that if A= R(k,m-1) and B=R(k-1,m) are both even then R(k,m) $\le$ A+B-1

Would be great if someone help in solving this one....

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

A counterexample would have to be a graph of order $A+B-1$ in which each vertex is incident with $A-1$ red edges and $B-1$ blue edges. In other words, the red graph would have $A+B-1$ vertices, each of degree $A-1.$ Since $A+B-1$ and $A-1$ are both odd numbers, this is impossible by the "handshake lemma".

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .