Combinando

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.

===== Solução =====

Se $G = (V,E)$ é um grafo conexo, não há o que fazer. Se não, considere $x,y \in V$ vértices quaisquer. Devemos concluir que existe um caminho que $\bar{G}$ que conecta esses dois vértices. Como $G$ não é conexo, existem $a,b\in G$ vértices que não são conectados por um caminho em $G$. Portanto, nem $x$ e nem $y$ devem ser adjacentes a esses dois vértices simultaneamente em $G$. Com isso, se $x$ e $y$ não são adjacentes ao mesmo vértice ($a$, por exemplo), então $\langle x,a,y\rangle$ será um caminho entre $x$ e $y$ em $\bar{G}$. Caso contrário, podemos supor que $x$ não é adjacente a $a$ e $y$ não é adjacente a $b$ em $\bar{G}$, de modo que $\langle x,a,b,y\rangle$ é um caminho entre $x$ e $y$ em $\bar{G}$. 


Além disso, existem grafos conexos cujo complementar é conexo. Por exemplo, considere o grafo $G =(V,E)$ com $V = \{1,2,3,4\}$ e $E = \{\{1,2\},\{2,3\},\{3,4\}\}$.

Combinando

User Tools

Site Tools

Page Tools