Bipartizione di un grafo a 9 nodi

Un grafo non orientato ha 9 nodi (0..8) e archi: 0—1; 1—2; 2—3; 3—4; 4—5; 5—6; 6—7; 7—8; 0—3; 2—5; 4—7. Il grafo è bipartito. Qual è la dimensione della parte più numerosa nell'UNICA bipartizione possibile (a meno di scambiare i nomi delle due parti)?