Condizioni

Le condizioni sono più facilmente definite immaginando il grafo connesso $G$ come:

dove $V_1,...V_k$ sono $k$ componenti connesse collegate da un singolo nodo $z\in V$.

Connettività

Se un grafo $G$ non orientato è connesso, allora è rispettata la condizione necessaria per cui: $$|E|\ge |V|-1$$ che è dimostrabile per induzione su $n=|V|$:

• Caso base, per $|V|=1$: non essendoci altri nodi $|E|=0$ e quindi $0\ge 1-1$
• Caso base, per $|V|=2$: essendo connessi $|E|=1$ e quindi $1\ge 2-1$
• Passo induttivo assumendo che valga fino a $n-1$:
  Rimuovendo $z$ si ottiene il sottografo $G[V\setminus \{z\}]$ che potrebbe però non essere connesso, ma se si considerano le $k$ componenti connesse come $G_i=(V_i,E_i)$ si ha che: $$|E|=\left(\sum _{i=1}^k|E_i|\right)+\mathrm{deg}(z)$$ che per ipotesi induttiva diventa: $$\begin{array}{rl}|E|& \ge \left(\sum _{i=1}^k|V_i|-1\right)+\mathrm{deg}(z)\\ & =\sum _{i=1}^k|V_i|-k+\mathrm{deg}(z)\\ & =\overbrace{|V|-1}+\mathrm{deg}(z)-k\ge |V|-1\end{array}$$ che è vero solo se $\mathrm{deg}(z)-k\ge 0$, ma è assurdo dire che $\mathrm{deg}(z)<k$ perchè vorrebbe dire che $z$ non è collegato con le $k$ componenti connesse, per cui $G$ non sarebbe connesso.

Quest'ultima condizione non basta per considerare un grafo come connesso, ma è possibile considerarlo tale se la condizione sufficiente è soddisfatta, ovvero se: $$\forall u\in V,\mathrm{deg}(u)\ge \frac{n-1}{2}$$ che è dimostrabile per assurdo, infatti se fosse vero e $z$ non fosse presente, allora con $k=2$: $$\begin{gathered} |V_1|\ge \mathrm{deg}(u_1)+\stackrel{u_1}{\overbrace{1}}\wedge |V_2|\ge \mathrm{deg}(u_2)+\stackrel{u_2}{\overbrace{1}} \\ \Downarrow \\ \begin{array}{rl}|V|& =|V_1|+|V_2|\\ & \ge \mathrm{deg}(u_1)+\mathrm{deg}(u_2)+2\\ & =n-1+2=|V|+1\end{array} \end{gathered}$$ che è assurdo, con $u_1\in V_1$ e $u_2\in V_2$.

Aciclicità

Se un grafo $G$ non orientato è aciclico, allora è rispettata la condizione necessaria per cui: $$|E|\le |V|-1$$ che è dimostrabile in maniera analoga alla connettività, da cui si ottiene: $$|E|\le |V|-1+\mathrm{deg}(z)-k\le |V|-1$$ che è vero, infatti sarebbe assurdo che $\mathrm{deg}(z)>k$ perchè altrimenti sarebbero presenti cicli.