Esistenza di un grafo di 15 vertici, data la valenza di alcuni suoi vertici.

[cloe009]

Salve,

ho il seguente esercizio sui grafi.

Se possibile disegnare un grafo che abbia 15 vertici che abbiano le seguenti caratteristiche:
3 vertici con valenza 4;
4 vertici con valenza 3;
6 vertici con valenza 2;
0 vertici con valenza maggiore delle precedenti.

Io ho provato a disegnarlo così,
ponendo su ogni vertice un numero indicando la sua valenza:


ma, la mia domanda è: siccome qui abbiamo dei dati quali, il numero dei vertici di un grafo e la valenza di alcuni di essi. Tramite questi dati, esiste un teorema o una funzione che mi permetta di calcolare, se sia possibile disegnare un grafo del genere, e se sì, di quanti lati deve essere? In modo da non andare a tentativi per poterlo disegnare.

mille grazie!

[vict85]

Non sono un esperto, ma non penso che esista un teorema che funzioni sempre. Senza dubbio i vertici di valenza due li puoi ignorare: ti basta costruire un grado senza di loro e poi aggiungerli nel mezzo di lati qualsiasi. I vertici di valenza 1 possono essere applicati in vari modi. Applicandoli a vertici con valenza 3 li si trasforma in valenza 2 rimanendo con un problema a 5 vertici (in caso questo non abbia soluzioni bisogna considerare anche le altre possibili applicazioni dei vertici di valenza 1). Nota che il problema non dice che ci sono due vertici di valenza 1, potrebbero essere anche di valenza 0.

Considerando il problema a 5 vertici, i 3 vertici di valenza 4 sono connessi a tutti gli altri, mentre i 2 rimanenti vertici di valenza 3 sono connessi solo ai vertici di valenza 4 e non tra di loro.