1. 2

Graph three colouring is known to be NP-Complete, so we should be able to use it to factor integers. Here’s how.

  1.