Potatura iterata dei vertici di grado al più 2

Sia G il grafo con vertici 1, ..., 10 e i seguenti archi: tutte le coppie {a, b} con $1 \le a < b \le 6$ tranne $\{1,2\}$, $\{3,4\}$, $\{5,6\}$ (12 archi, un ottaedro sui vertici 1..6), più gli archi 7-8, 7-1, 8-9, 8-2, 9-10, 9-3, 10-1, 10-4. Si ripete l'operazione: «scegli un vertice di grado minore o uguale a 2 ed eliminalo insieme ai suoi archi», finché nessun vertice ha grado $\le 2$. Quanti vertici restano alla fine? (Il risultato non dipende dall'ordine delle eliminazioni.)