Graph Theory Question - Triangle and angle

578 Views Asked by At

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.

1

There are 1 best solutions below

0
On BEST ANSWER

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.