Индуктивное доказательство того, что определенный алгоритм не претендует на то, чтобы не 3-раскрашиваемый граф был 3-раскрашиваемым

Question

В теоретической информатике нам был дан определенный алгоритм в псевдокоде:

G = (V, E) is a undirected graph
while(G has vertices with degree <=2)
    remove those vertices
if(G is empty)
    Graph is 3-colorable
else
    Graph may or may not be 3-colorable

Задача состоит в том, чтобы доказать, что граф, не являющийся 3-раскрашиваемым, не считается таковым этималгоритм. Я пытался показать, что каждый не 3-окрашенный граф имееткак подграф, и поэтому имеет в какой-то момент только вершины со степенью> 2, но позже узнал, что это не обязательно так, поэтому я снова на первом месте.

Намек был дан нам былодоказательство это индуктивно, но я ничего не понимаю.