Lezione 19

Alcune costruzioni con i grafi

Definizione 19.1   Sia $G=(V,E)$ un grafo, definiamo alcuni grafi costruiti a partire da $G$:

• (cancellazione di un lato) se $e\in E$ denotiamo
  $$G-e=(V,E\setminus\{e\})$$

• (aggiunta di un lato) se $e\in {V \choose 2}\setminus E$ denotiamo
  $$G+e=(V,E\setminus\{e\})$$

• (cancellazione di un vertice) se $v\in V$ denotiamo
  $$G-v=(V\setminus\{v\},\{e\in E\mid v\notin e\})$$

• (divisione di un lato) se $e=\{u,v\}\in E$ denotiamo
  $$G\%e=(V\cup\{z\},E\setminus\{e\}\cup\{\{u,z\},\{v,z\}\})$$
  essendo $z\notin V$.

Esercizio 19.1   Si provi che se $G$ è connesso, allora per ogni $e\in E(G)$, anche $G\%e$ è connesso.
Soluzione

Esercizio 19.2   Si provi che per ogni vertice $v$ si ha che $C_n-v\oldcong P_{n-1}$.
Soluzione

Definizione di grafo 2-connesso

Definizione 19.2   Sia $G$ un grafo, diremo che $G$ è $2$-connseeo se $\left\vert V(G)\right\vert\ge3$ e per ogni $v\in V(G)$ si ha che $G-v$ è connesso.

Esercizio 19.3   Si provi che ogni grafo hamiltoniano è $2$-connesso.
Soluzione

Esercizio 19.4   Si provi che se $f:G\to G'$ è un isomorfismo, allora per ogni $v\in V(G)$ ed $e\in E(G)$ si ha che $G-v\oldcong G'-f(v)$, $G-e\oldcong G'-f(e)$, $G\%e\oldcong G'\%f(e)$.
Soluzione

Esercizio 19.5   Si provi che se $e\in E(C_n)$ allora $C_n\%e \oldcong C_{n+}1$.
Soluzione

Esercizio 19.6   Si provi che se $e\in E(P_n)$ allora $P_n\%e \oldcong P_{n+1}$.
Soluzione

Proposizione 19.3   Sia $G$ un grafo $2$-connesso e $e\in E(G)$. Allora $G-e$ è connesso.

Dimostrazione.  Siano $u,v\in V$. Dobbiamo provare che esiste una passeggiata tra $v$ e $u$ che non contiene il lato $e$. Si hanno due casi

1. $e\ne \{u,v\}$;
2. $e=\{u,v\}$.

Nel primo caso, sia $x$ un estremo di $e$ diverso da $u$ e $v$ (i.e. $e=\{x,y\}$ con $x\ne u$ e $x\ne v$) allora $u,v\in V(G-x)$. Dato che $G$ è $2$-connesso, $G-x$ è connesso, e quindi esiste una passeggiata in $G-x$ che congiunge $u$ e $v$. Dato che $x\in e$, $e\notin E(G-x)$ quindi questa passeggiata non contenere il lato $e$.

Nel secondo caso, sia $w\in V(G)\setminus \{u,v\}$ (esiste perché $\left\vert V(G)\right\vert\ge3$). Dato che $G$ è $2$-connesso esiste una passeggiata $P$ tra $u$ e $w$ in $G-u$ (chiaramente tale passeggiata non passa per $e$). Per lo stesso motivo esiste una passeggiata tra $w$ e $v$ in $G-u$ (anche questa passeggiata non può contenere il lato $e$). Congiungendo queste due passeggiate si ottiene una passeggiata che congiunge $u$ e $v$ e che non passa per $e$.     $\square$

Osservazione 19.4   Dalla proposizione precedente segue in particolare che ogni grafo $2$-connesso è connesso.

Prima caratterizzazione dei grafi 2-connessi

Teorema 19.5 (prima caratterizzazione dei grafi $2$-connessi)   Un grafo $G$ è $2$-connesso se e solo se ogni coppia di vertici di $G$ è contenuta in un ciclo. Ossia per ogni $v,w\in V(G)$ esiste un ciclo $(v_0,v_1,\dots,v_n=v_0)$ in $G$ che passa per i vertci $v$ e $w$.

Seconda caratterizzazione dei grafi 2-connessi

Lemma 19.6   Sia $G$ un grafo $2$-connesso allora per ogni $e\in E$ anche $G\%e$ è $2$-connesso.

Dimostrazione.  Sia $e=\{x,y\}$ e $v\in V(G\%e)=V(G)\cup\{z\}$. Si hanno tre casi:

1. $v=z$;
2. $v=x$ o $v=y$;
3. $v\ne x$, $v\ne y$ e $v\ne z$

Nel primo caso, $G\%e-v=G\%e-z=G-e$, infatti dalle definizioni si ha

$$V(G\%e-z) = V(G\%e)\setminus \{z\} = (V(G)\cup\{z\})\setminus \{z\} =V(G) = V(G-e)$$

$$E(G\%e-z) = \{a\in E(G\%e) \mid z\notin a\} =$$

$$\big( (E(G)\setminus\{e\})\cup\{\{z,x\},\{z,y\}\} \big)\setminus \{a\mid z\in a\} =$$

$$E(G)\setminus\{e\}=E(G-e)$$

Pertanto $G\%e-v$ è connesso per la proposizione 19.3

Nel secondo caso, supponiamo che $v=y$ (l'altro caso si ottiene per simmetria, scambiando $x$ e $y$). Osserviamo che $G-y$ è un sottografo di $G\%e - y$. Infatti

$$V(G-y) = V(G)\setminus\{y\}$$

$$V(G\%e - y) = V(G\%e)\setminus\{y\}=(V(G)\cup\{z\})\setminus\{y\} = V(G-y)\cup\{z\}$$

$$E(G-y) = E(G)\setminus\{a\mid y \in a\}$$

$$E(G\%e-y) = E(G\%e)\setminus\{a\mid y \in a\} =$$

$$\big((E(G)\setminus\{e\})\cup\{\{z,x\},\{z,y\}\}\big)\setminus\{a\mid y \in a\} =$$

$$(E(G)\setminus\{a\mid y \in a\})\cup\{\{x,z\}\}= E(G-v)\cup\{\{x,z\}\}=$$

Ma allora dato che ogni $G-v$ è $2$-connesso, $G-v$ è connesso e quindi ogni vertice di $G-v$ è congiungibile in $G-v$, e quindi in $G\%e - y$ al vertice $x\in V(G-v)$. D'altra parte, l'unico altro vertice di $G\%e - y$ è $z$ che è congiungibile a $x$ in $G\%e - y$, dato che $\{x,z\}\in E(G\%e-y)$. Tutti i vertici sono quindi congiungibili tra loro.

Nel terzo caso $G\%e - v= (G-v)\%e$ è connesso in quanto ottenuto dal grafo connesso $G-v$ suddividendo un suo lato ($G-v$ è connesso).     $\square$

Lemma 19.7   Sia $G$ un grafo $2$-connesso allora per ogni $e\in {V \choose 2}\setminus E$ anche $G+e$ è $2$-connesso.

Dimostrazione.  Segue dal fatto che per ogni vertice $v\in V(G+e)=V(G)$ il grafo $(G+e)-v$ ha gli stessi vertici di $G-v$ e contiene tutti i lati di $G-v$. Dato che quest'ultimo è connesso, lo ànche $(G+e)-v$.     $\square$

Teorema 19.8   Un grafo finito $G$ è $2$-connesso se e solo se è isomorfo ad un grafo ottenuto a partire da $C_3$ con una successione finita di suddivisioni di ed aggiunzioni di lati.

Dimostrazione.  Dato che $C_3$ è $2$-connesso, i due lemmi precedenti provano che ogni grafo ottenuto da $C_3$ aggiungendo e suddividendo lati è $2$-connesso.

Proviamo l'implicazione opposta. Per semplicità diciamo che un grafo è costruibile se è ottenuto da $C_3$ con un numero finito di aggiunzioni e suddivisioni di nodi. Consideriamo l'insieme

$${\cal G}= \{H\mid H$$    è sottografo costruibile di $$G\}.$$

usando l'esercizio 19.5, si prova che ogni ciclo è costruibile, d'altra parte dal primo teorema di caratterizzazione segue, in particolare, che $G$ contiene dei cicli. Ma allora ${\cal G}\ne\varnothing$. Sia allora $H_0\in{\cal G}$ un grafo che massimizza il numero dei lati ($G$ è finito!), ossia tale che

$$\left\vert E(H_0)\right\vert \ge \left\vert E(H)\right\vert\quad \forall H\in {\cal G}.$$ (11)

Proviamo che $H_0=G$ da cui segue evidentemente la tesi.

$V(H_0)=V(G)$. Supponiamo per assurdo che esista $v\in V(G)\setminus V(H_0)$. $G$ è connesso, esiste quindi un cammino $P=(v_0,\dots,v_m)$ che congiunge $v$ ad un vertice di $H_0$. Sia $v_i$ il primo vertice di questo cammino tale che $v_i\in V(H_0)$. Chiamiamo $w=v_i$ e $u=v_{i-1}$ ($i>0$ dato che $v_0=v\notin V(H_0)$), allora $e=\{u,w\}\in E(G)$ , $w\in V(H_0)$ e $u\notin V(H_0)$.

Il grafo $G-w$ è connesso e, dato che $H_0$ ha almeno tre vertici, esistono vertici di $H_0$ diversi da $w$. Sia allora $Q=(u_0,\dots,u_k)$ un cammino in $G-w$ che congiunge $u$ ad un vertice di $H_0$ ed i cui altri vertici sono tutti fuori di $H_0$ (vedi figura 7), ossia $u_0=u$, $u_k\in V(H_0)$ e $v_i\notin V(H_0)$ per ogni $i<k$. Consideriamo il grafo $H_1$ definito da:

Figura 7: Come costruire un cammino che ha solo due punti in comune con $H_0$

$$V(H_1) = V(H_0) \cup \{u=u_0,\dots,u_{k-1}\}$$

$$E(H_1) = E(H_0)\cup \big\{e=\{w,u_0\},\{u_0,u_1\},\dots,\{u_{k-1},u_k\}\big\}$$

Chiaramente $H_1$ è un sottografo di $G$ e $\left\vert E(H_1)\right\vert>\left\vert(H_0)\right\vert$. Se proviamo che $H_1$ è ottenuto da $H_0$ con un numero finito di suddivisioni e di aggiunzioni di lati si ha che $H_1\in{\cal G}$ e quindi un assurdo. Ma ora si hanno due casi:

1. $\{w,u_k\}\in E(H_0)$
2. $\{w,u_k\}\notin E(H_0)$

Nel primo caso $H_1$ è ottenuto suddividendo $k$ volte il lato $\{w,u_k\}$ e quindi aggiungendo di nuovo il lato $\{w,u_k\}$, nel secondo caso $H_1$ è ottenuto aggiungendo il lato $\{w,u_k\}$ e quindi dividendolo $k$ volte (vedi figura 8).

Figura 8: Il grafo $H_1$ è ottenuto da $H_0$ o aggiungendo un lato e quindi suddividendolo oppure suddividendo un lato già esistente e quindi riaggiungendolo.

$E(H_0)=E(G)$. Supponiamo per assurdo che $e\in E(G)\setminus E(H_0)$, allora, visto che per il punto precedente $V(H_0)=V(G)$, necessariamente $e\in{V(H_0) \choose 2}$, si può allora costruire il grafo $H_1=H_0+e$ che è un sottografo di $G$. D'altra parte $H_1$ è ottenuto da $H_0$ aggiungendo un lato, quindi è costruibile, ovvero $H_1\in{\cal G}$. Ma $\left\vert E(H_1)\right\vert=\left\vert E(H_0)\right\vert+1$, che contraddice la (11).     $\square$

Esercizio 19.7   Siano $G=(V,E)$ e $G'=(V'.e')$ due grafi. Si denoti con $G\cup G'$ il grafo tale che $V(G\cup G') = V\cup V'$ e $E(G\cup G')=E\cup E'$. Si provi che se $G$ e $G'$ sono connessi e $V\cap V'\ne\varnothing$ allora $G\cup G'$ è connesso.
Soluzione

Esercizio 19.8   Si provi che se $G$ e $G'$ sono 2-connessi e $\left\vert V\cap V'\right\vert\ge2$ allora $G\cup G'$ è 2-connesso.
Soluzione

Esercizio 19.9   Sia $k\ge1$, si dice che un grafo $G=(V,E)$ è $k$-connesso se per ogni $v_1,\dots,v_{k-1}\in V$ si ha che $G-v_1-v_2-\dots-v_{k-1}$ è connesso. Si osservi che $1$-connesso è sinonimo di connesso.

Si provi che $G$ è $k-connesso$ se e solo se per ogni $v\in V$ $G-v$ è $k-1$-connesso.
Soluzione

Esercizio 19.10   Si determinino condizioni sufficienti affinché l'unione di due grafi $k$-connessi sia ancora $k$-connesso.
Soluzione

Esercizio 19.11   Per ogni $n\in \mathbb{N}$ sia $G_n=(V_n,E_n)$ un grafo connesso e si supponga che $V_n\subseteq V_{n+1}$ per ogni $n$. Si provi che allora $G=\bigcup_{n\in\mathbb{N}} G_n$ è connesso.
Soluzione

Esercizio 19.12   Per ogni $n\in \mathbb{N}$ sia $G_n=(V_n,E_n)$ un grafo connesso e si supponga che $V_n\cap V_{n+1}\ne\varnothing$ per ogni $n$. Si provi che allora $G=\bigcup_{n\in\mathbb{N}} G_n$ è connesso.
Soluzione

Esercizio 19.13   Per ogni $n\in \mathbb{N}$ sia $G_n=(V_n,E_n)$ un grafo $k$-connesso e si supponga che $\left\vert V_n\cap V_{n+1}\right\vert\ge k$ per ogni $n$. Si provi che allora $G=\bigcup_{n\in\mathbb{N}} G_n$ è $k$-connesso.
Soluzione