[SENIOR 2006 - C3] Grafi cubici senza ponti

[MindFlyer]

(Petersen)
Dimostrare che ogni grafo 3-regolare senza ponti ha un perfect matching.

Nota: un ponte è un arco che, se eliminato, aumenta il numero di componenti connesse del grafo.

[MindFlyer]

Dunque, diamo le altre definizioni.

Un grafo 3-regolare è un grafo in cui ogni vertice ha 3 archi.

Un perfect matching o 1-fattore di un grafo G=(V,E) è un insieme di archi $ E'\subseteq E $ tale che ogni nodo di G è vertice di uno ed un solo arco di E'.

[enomis_costa88]

Visto che non lo guarda nessuno ci provo..

Cancelliamo n nodi dal grafo (con 2k nodi) e gli archi che questi formano.
Rimarranno 2k-n=j+k nodi e almeno 3(k-n)=3j archi.

Claim:
Il numero di componenti connesse con un numero dispari di nodi in un grafo (con j+k nodi,3j archi, e in più le condizioni sui gradi dei nodi) è al più n=k-j.

Ipotizzo siano di più.
Ciascuna componente connessa ha almeno due nodi con grado minore di 3 (altrimenti avrei un ponte nel grafo di partenza).

Le componenti connesse con un numero pari di nodi le posso connettere a quelle con un numero dispari aggiungendo un’arco tra due vertici di grado minore di 3.
Ottengo ancora un grafo con j+k nodi e più di 3j archi; inoltre saranno ancora rispettate le condizioni sul grado di ciascun nodo.

Posso quindi supporre che tutte le componenti connesse abbiano un numero dispari di nodi.

Dimostro facilmente che il numero massimo di archi che può avere una componente connessa con 2i+1 nodi è 3i.

Sia quindi $ k_i $ il numero di componenti connesse con i vertici;
Sia E il numero di archi.
Sia C il numero di componenti connesse.

So che:
i) $ \sum k_i*3i\ge E \ge 3j; \sum k_i*i\ge j $
ii) $ C =\sum k_i>k-j $
E per doppio conteggio sul numero dei nodi:
iii) $ k+j= \sum k_i(2i+1) $

Da cui facilmente:
$ \sum k_i+2\sum k_i*i>k-j+2j=k+j= \sum k_i(2i+1) $
Ma questo è assurdo.

Quindi il claim è dimostrato e per il teorema di Tutte esiste un perfect matching.