24. Grafo di 9 vertici
Un grafo è costituito da vertici e lati. I vertici sono generalmente rappresentati con piccoli cerchi e i lati con linee che congiungono due vertici.
Il grado di un vertice è il numero di lati che partono (o terminano) da quel vertice.
Considerate un grafo che ha 9 vertici e in cui ogni vertice ha grado 5 oppure 6.
Dimostrate che almeno 5 vertici hanno grado 6 oppure almeno 6 vertici hanno grado 5.
..Penso che il problema sia mal formulato.
Dalla frase
intesa in senso inclusivo ricaviamo 6 possibili tipi di grafo, uno con 9 vertici di grado 6, un altro con 7 vertici di grado 6 e 2 di grado 5, un altro… Ovvero, in modo sintetico e più leggibile:ogni vertice ha grado 5 oppure 6
9x6....(7x6 e 2x5)....(5x6 e 4x5)....(3x6 e 6x5)....(1x6 e 8x5)....9x5
di cui un esempio con (1x6 e 8x5) è nella figura sotto.
Anche prendendo la frase “ogni vertice ha grado 5 oppure 6” in senso esclusivo, cioè togliendo il primo e l’ultimo caso in cui tutti i vertici hanno lo stesso grado, rimangono 4 tipi di grafo, mentre dal testo sembrerebbe che solo il terzo e quarto tipo siano possibili.