8
$\begingroup$

I was asked the following problem and have solved the first - but could not "deduce..." any hints would be great.

Show that a complete graph with $2^t+1$ vertices cannot be expressed as the union of $t$ bipartite graphs. Deduce that in any set of $2^t+1$ points in the plane we can find a triangle with an angle of at least $(1-1/t)\pi$ radians.

$\endgroup$
1
$\begingroup$

If you just want a hint, go with this:

Partition the edges of your complete graph by their slope, thus expressing the graph as the union of $t$ subgraphs, each with nearly parallel edges.

If you need more details—check the revision history. 😉

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.