Skip to main content
2 of 4
edited tags
Dr Shello
  • 1.2k
  • 5
  • 17

Labelled spanning trees without edge crossings

Draw the complete graph $K_n$ in the plane with every edge a straight line and randomly label the edges $0$ or $1$. Does this graph always have a spanning tree with no edges crossing and edge-labels either all $0$ or all $1$?

Dr Shello
  • 1.2k
  • 5
  • 17