OliForum Matematico

Vorrei trovare tutti i grafi G tali che ogni grafo di grado minimo sufficientemente grande contiene un sottografo uguale a G... chi mi da una mano?

scusa edriv che forse è una domanda idiota: che cos 'è il grado di un grafo?è il numero di lati? poichè vorrei pensare al problema che poni..vorrei essere sicuro di pensare al problema che poni..grazie e scusa
Ciao!

Il grado di un nodo del grafo è il numero di lati che partono da quel nodo.

Se un grafo ha grado minimo 4, ad esempio, vuol dire che da ogni nodo partono almeno 4 lati (e c'è un nodo da cui partono esattamente 4 lati, altrimenti il grado minimo sarebbe superiore).

Tanto vale che definisco bene tutto allora.
Dati due grafi H,G, un morfismo di grafi da H a G è una funzione f dai vertici di H ai vertici di G tale che, se a,b sono vertici di H collegati da un lato, anche f(a) ed f(b), che sono vertici di G, sono collegati da un lato.

Allora chiedo di trovare tutti i grafi H per cui esiste un k tale che:
se G è un grafo con grado minimo maggiore o uguale a k, allora esiste un morfismo iniettivo da H in G.

Grazie!

Intanto G dev'essere una foresta: per un famoso teorema di Erdos, esistono grafi con girth arbitrariamente alto e numero cromatico arbitrariamente alto. Una facile conseguenza è che questi grafi contengono sottografi che hanno grado minimo arbitrariamente alto. E naturalmente, il girth di un sottografo non può diminuire.

Dimostrare che tutte le foreste vanno bene, è un facile esercizio: si fissi un insieme di alberi (radicati), si prenda un grafo di grado minimo sufficientemente alto, e si costruisca ogni albero a partire dalla radice, e andando avanti livello per livello... A voi i dettagli!

Ok... ma però

il problema consisteva alla fine del trovare una dimostrazione (magari elementare ed elegante) che esistono grafi di mindegree e girth (dove girth è la lunghezza del più piccolo ciclo) arbitrariamente alti.
Se poi questo è un corollario di un teoremone di Erdos non posso farci niente.

Comunque adesso siamo sicuri del claim: i grafi sono tutte e sole le foreste. La dimostrazione di Erdos usa una tecnica probabilistica, ma non la definirei non elementare. Forse esiste una scorciatoia per il grado minimo anziché il numero cromatico, perché apparentemente il problema è più semplice (dire che un grafo è localmente un albero forza il suo numero cromatico locale a 2, ma non dice nulla sul grado minimo locale).

Ah, con un po' più di fatica si dimostra che lo stesso risultato vale anche se al posto del grado minimo prendi il grado medio.