Conexidade
Fazer a lista de caminhos e ciclos pode ajudar.
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$.
1 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?
2 Dado $n$ um número natural, $K_n$ é conexo? E seu grafo complementar?
3 Considere $G$ um grafo conexo tal que $\delta(G) = 1$ e $\Delta(G) = 2$. Que tipo de grafo é esse?
4 Mostre que um grafo $G$ é conexo ou seu complementar $\bar{G}$ é conexo. Esse “ou” é mutuamente exclusivo? Solução
5 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. Solução
6 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? Solução
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$.
7 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.
7.1 Se $x,y \in V$ são vértices tais que $C_x \cap C_y \neq \emptyset$, então $C_x = C_y$.
7.2 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$.
7.3 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$.
8 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$.
