а) Первый способ. Обозначим  p₁ = 13,  p₂ = 17,  p₃ = 19,  p₄ = 23,  p₅ = 29,  p₆ = 31,  p₇ = 37.  Занумеруем точки числами от 1 до 200 и окрасим отрезки, соединяющие точки, номера которых сравнимы по модулю p_i, в i-й цвет (условие непротиворечиво:  НОК(p_i, p_j) > 200).  Тогда в группе точек с номерами, сравнимыми с данным числом по модулю p_i, Петя сможет окрасить в i-й цвет не более одной. Значит, всего в i-й цвет он окрасит не больше p_i точек. Но  p₁ + ... + p₇ < 200.  Противоречие.   Второй способ. Докажем по индукции следующее утверждение: если число цветов n, а число точек не меньше 2ⁿ, то ответ отрицательный.

  База  (n = 1)  очевидна.

  Шаг индукции. Разобьём точки на два множества, состоящие не менее чем из  2^n–1  точек каждое. В каждом из множеств покрасим отрезки в  n – 1  цвет в соответствии с индуктивным предположением. Все отрезки, соединяющие точки из разных множеств, покрасим оставшимся цветом. Если в каком-то из двух множеств нет точек, покрашенных в последний цвет, то "плохой" отрезок существует по предположению индукции. Если же в обоих множествах есть точки последнего цвета, то соединяющий их отрезок – "плохой".   б) Покажем, что это не удастся сделать даже для 121 точки. Отождествим точки с точками конечной плоскости 11-го порядка. Выделим на ней 10 направлений (всего их 12) и все отрезки i-го направления покрасим в i-й цвет. Тогда на каждой прямой i-го направления только одна из 11 точек может иметь i-й цвет, то есть точек i-го цвета не больше 11. Но  10·11 < 121.  Противоречие.

Не всегда (в обоих случаях).