Skip to main content

Draw the complete graph $K_n$ in theon a plane [added: in general position]in general position 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$?

Draw the complete graph $K_n$ in the plane [added: in general position] 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$?

Draw the complete graph $K_n$ on a plane in general position 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$?

Post Reopened by Fedor Petrov, Gil Kalai, Sergei Ivanov, Tony Huynh, Joseph O'Rourke
added 33 characters in body
Source Link
Dr Shello
  • 1.2k
  • 5
  • 17

Draw the complete graph $K_n$ in the plane [added: in general position] 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$?

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$?

Draw the complete graph $K_n$ in the plane [added: in general position] 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$?

Post Closed as "too localized" by S. Carnahan
edited tags
Link
Dr Shello
  • 1.2k
  • 5
  • 17
Source Link
Dr Shello
  • 1.2k
  • 5
  • 17
Loading