Teorema dei matrimoni per grafi
Salve a tutti
In tantissimi libri e dispense di teoria dei grafi (e non solo) si parla del teorema di Hall, noto anche come il teorema dei matrimoni, che dice (lo formulo nella forma di teoria dei grafi):
Sia $G=(V_1 \cup \V_2,E)$ un grafo bipartito. Esiste un accoppiamento $M \subseteq E$ che copre tutto $V_1$ $\iff$ per ogni $A \subseteq V_1$ il numero di vicini di $A$ è maggiore o uguale di $|A|$.
E questo è ok, la dimostrazione necessaria è una semplice induzione. Quella verso sinistra a seconda di dove lo si vada a cercare viene data in tanti modi diversi.
In quasi tutti i testi che ho consultato si fa sempre riferimento al fatto che questo teorema possa essere visto come conseguenza del teorema di Menger (anche questo dato in forma di grafi nella versione sui vertici):
Siano $u$ e $v$ vertici non adiacenti di un grafo $G$. Il minimo numero di vertici che separa $u$ da $v$ è uguale al massimo numero di sentieri (path) disgiunti da $u$ a $v$ (disgiunti a meno degli estremi).
La mia domanda è questa, come posso fare a dimostrare Hall usando Menger?
Come detto le dispense su cui ho studiato teoria dei grafi dicono che sia facile da fare... ma non ci riesco. Ovviamente andrà usato per dimostrare il verso sufficiente. Generalmente tale dimostrazione la si fa per assurdo. Quindi mi sono detto:
Per assurdo valga che ogni accoppiamento di $G$ non ricopra tutto $V_1$. Consideriamo l'accoppiamento massimo (non so se sia importante) $M$ allora esiste almeno un $v \in V_1$ non coperto da tale accoppiamento. Sia $u \in V_1$ e $u \ne v$ sarà ovviamente disgiunto da $v$.
A questo punto secondo me devo buttarci dentro Menger e magicamente giungere alla conclusione della dimostrazione. L'unica relazione che però mi viene in mente tra numero di sentieri massimi tra $u$ e $v$ e i loro vicini è che appunto i primi saranno sicuramente minori o uguali dei secondi (che è banale come cosa).
In tantissimi libri e dispense di teoria dei grafi (e non solo) si parla del teorema di Hall, noto anche come il teorema dei matrimoni, che dice (lo formulo nella forma di teoria dei grafi):
Sia $G=(V_1 \cup \V_2,E)$ un grafo bipartito. Esiste un accoppiamento $M \subseteq E$ che copre tutto $V_1$ $\iff$ per ogni $A \subseteq V_1$ il numero di vicini di $A$ è maggiore o uguale di $|A|$.
E questo è ok, la dimostrazione necessaria è una semplice induzione. Quella verso sinistra a seconda di dove lo si vada a cercare viene data in tanti modi diversi.
In quasi tutti i testi che ho consultato si fa sempre riferimento al fatto che questo teorema possa essere visto come conseguenza del teorema di Menger (anche questo dato in forma di grafi nella versione sui vertici):
Siano $u$ e $v$ vertici non adiacenti di un grafo $G$. Il minimo numero di vertici che separa $u$ da $v$ è uguale al massimo numero di sentieri (path) disgiunti da $u$ a $v$ (disgiunti a meno degli estremi).
La mia domanda è questa, come posso fare a dimostrare Hall usando Menger?
Come detto le dispense su cui ho studiato teoria dei grafi dicono che sia facile da fare... ma non ci riesco. Ovviamente andrà usato per dimostrare il verso sufficiente. Generalmente tale dimostrazione la si fa per assurdo. Quindi mi sono detto:
Per assurdo valga che ogni accoppiamento di $G$ non ricopra tutto $V_1$. Consideriamo l'accoppiamento massimo (non so se sia importante) $M$ allora esiste almeno un $v \in V_1$ non coperto da tale accoppiamento. Sia $u \in V_1$ e $u \ne v$ sarà ovviamente disgiunto da $v$.
A questo punto secondo me devo buttarci dentro Menger e magicamente giungere alla conclusione della dimostrazione. L'unica relazione che però mi viene in mente tra numero di sentieri massimi tra $u$ e $v$ e i loro vicini è che appunto i primi saranno sicuramente minori o uguali dei secondi (che è banale come cosa).