===== Conexidade =====
<WRAP tip>
Fazer a lista de [[lista:caminhosciclos|caminhos e ciclos]] pode ajudar.
</WRAP>

<WRAP info>
Dizemos que um grafo $G = (V,A)$ é **conexo** se, dados $x,y\in V$ vértices do grafo, existir um caminho $\langle v_1,v_2,\dots,v_n\rangle$ de $G$ com $v_1=x$ e $v_2=y$. Nessas condições, dizemos que $\langle v_1,v_2,\dots,v_n\rangle$ conecta ou liga os vértices $x$ e $y$. O comprimento do menor caminho ligando esses dois vértices é dito ser a **distância** entre $x$ e $y$, sendo representado por $d(x,y)$ (se $x=y$, denotamos $d(x,y)=0$). Quando o grafo não é conexo, dizemos que ele é **desconexo**, existindo vértices $x,y \in V$ que não são ligados por nenhum caminho de $G$. Nesse caso, escrevemos $d(x,y) = \infty$.
</WRAP>

**~~#~~** Considere o grafo abaixo cujo conjunto de vértices corresponde a todos os pontos pretos abaixo e cujas arestas entre eles estão representadas. Esse grafo é conexo?

{{ :lista:desconexo.png?400 |}}

**~~#~~** Dado $n$ um número natural, $K_n$ é conexo? E seu grafo complementar?

**~~#~~** Considere $G$ um grafo conexo tal que $\delta(G) = 1$ e $\Delta(G) = 2$. Que tipo de grafo é esse?

**~~#~~** Mostre que um grafo $G$ é conexo ou seu complementar $\bar{G}$ é conexo. Esse "ou" é mutuamente exclusivo? <wrap help>[[Solucao:complementarconexo|Solução]]</wrap>

**~~#~~** Considere $G$ um grafo com $n\in\mathbb{N}$ vértices e tal que $\delta(G) \geq \frac{n-1}{2}$. Mostre que $G$ é conexo. <wrap help>[[Solucao:grauminimo|Solução]]</wrap>

**~~#~~** Considere $G=(V,A)$ um grafo conexo com conjunto de vértices finito e com $|V|\geq 2$. Mostre que existem dois vértices distintos $x,y\in V$ tais que o subgrafo induzido de $G$ a $V\setminus \{x\}$ e o subgrafo induzido de $G$ a $V\setminus \{y\}$ são conexos. Isso é verdade para grafos conexos com um conjunto infinito de vértices? <wrap help>[[Solucao:verticeestável|Solução]]</wrap>

<WRAP info>
Seja $G = (V,A)$ um grafo e fixe $x \in V$. O conjunto $C_x = \{y \in V : d(x,y)<\infty\}$ é dito ser a **componente conexa** do vértice $x$ no grafo $G$.
</WRAP>

**~~#~~** Seja $C_x$ a componente conexa de $x$ no grafo $G = (V,A)$. Mostre que $C_x \neq \emptyset$ e que o subgrafo induzido de $G$ a $C_x$ é conexo.

**~~#.#~~** Se $x,y \in V$ são vértices tais que $C_x \cap C_y \neq \emptyset$, então $C_x = C_y$.

**~~#.#~~** Conclua que o conjunto $\mathcal{C} = \{C_x : x \in V\}$ é uma partição de $V$ (isto é, os elementos de $\mathcal{C}$ são dois a dois disjuntos e $\displaystyle \bigcup_{C\in\mathcal{C}}C = X$). Os elementos de $\mathcal{C}$ são conhecidos como **componentes conexas do grafo** $G$.

**~~#.#~~** Mostre que uma componente conexa de um grafo $G$ é um subgrafo maximal conexo de $G$. Isto é, se $H$ é um subgrafo conexo de $G$, então $H$ é subgrafo de uma componente conexa de $G$.

**~~#~~** Mostre que um grafo $G = (V,A)$ é conexo se, e somente se, dados $V_1,V_2\subset V$ com $V_1 \cup V_2 = V$ e $V_1 \cap V_2 = \emptyset$, existe $\{a,b\}\in A$ com $a\in V_1$ e $b\in V_2$.