You thief, I generalized your stupid problem!

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Avatar utente
karlosson_sul_tetto
Messaggi: 1452
Iscritto il: 10 set 2009, 13:21
Località: Napoli

You thief, I generalized your stupid problem!

Messaggio da karlosson_sul_tetto »

Sia dato $G$ un grafo infinito avente un preciso $\Delta (G)=k$ (ovvero c'è $k$ tale che il numero di lati che partono da ciascun vertice è $\leq k$). Dimostrare che è possibile assegnare ad ogni vertice $v_i$ un insieme finito $A_i$ (di numeri interi, reali, fiorellini, non importa) in modo che $A_i \bigcap A_j=0 \iff v_i\; \text{e} \;v_j$ sono collegati.

Hint:
Testo nascosto:
Un caso più semplice è quando $G$ è privo di cicli, ovvero è un albero infinito.
"Inequality happens"
---
"Chissa se la fanno anche da asporto"
Rispondi