Combinatoria estremale dei grafi

Combinatoria estremale dei grafi §

Vogliamo rispondere alla seguente domanda: Qual è il numero massimo di archi $D(n)$ affinché un grafo di ordine $n$ sia disconnesso?

Supponiamo abbia solo due componenti connesse, se infatti ne avesse di più, potrei aggiungere archi collegando le componenti connesse, mantenendo il grafo disconnesso. Le componenti connesse partizionano i vertici in due sottoinsiemi di cardinalità $x$ ed $n-x$. Supponiamo di aver massimizzato gli archi nelle due componenti, ovvero sono i grafi $K_n$ e $K_{n-x}$, il numero di archi è in totale:

$$|E(K_x)|+|E(K_{n-x})|=\frac{x(x-1)}{2}+\frac{(n-x)(n-x-1)}{2}$$

non ci resta che ottimizzare questa quantità rispetto ad $x$ vincolato a valori $0<x<n$. Un punto stazionario del polinomio è $x=\frac{n}{2}$, (si può scegliere la parte intera superiore o inferiore), che tuttavia è un minimo! dalla convessità risulta che l’ottimo è sui bordi (si possono usare le Condizioni di ottimalità Duali KKT). Dunque

$$D(n)=\frac{(n-1)(n-2)}{2}=\left(\genfrac{}{}{0ex}{}{n-1}{2}\right)$$

caso n = 4

Si può far il ragionamento più smart minimizzando il numero di archi tolti che rendono possibile la disconnessione: $x(n-x)$, che ha minimo proprio in $x=1$ e $x=n-1$. In questi punti il numero di archi è:

$$D(n)=\frac{(n-1)(n-2)}{2}=\left(\genfrac{}{}{0ex}{}{n-1}{2}\right)$$

Corollario Se $G$ ha ordine $>D(n)$ allora è connesso.