Fiz uma solução do exercicio 9.9, mas acho que está "torta". Opniões?
E 9.9 Mostre que $\nabla(X \oplus Y) = \nabla(X) \oplus \nabla(Y)$ para quaisquer conjuntos X e Y de vértices de um grafo.
Vamos mostrar usando indução em $|X|$ e $|Y|$.
Considere $|X|=|Y|=1$. Se $X \cap Y \neq \emptyset$, então $X=Y$, e a diferença simétrica entre os dois é vazia. Logo, $\nabla(X \oplus Y) = \emptyset$. Mas $\nabla(X) = \nabla(Y)$, e portanto$\nabla(X) \oplus \nabla(Y) = \emptyset$, logo a igualdade vale.
Considere agora $X \cap Y = \emptyset$. Seja $X=\{x\}$ e $Y=\{y\}$. Não temos uma aresta comum aos dois portanto $\nabla(X \oplus Y)=\nabla(X) \oplus \nabla(Y)$.
Tome agora $|X| > 1, |Y| > 1, X \neq Y$.
Seja $x \in X$, e considere $X' = X \setminus \{x\}$.
Por hipotese de indução, $\nabla(X' \oplus Y) = \nabla(X') \oplus \nabla(Y)$.
Temos então que se $x \in X$ e $x \notin Y$, então $\nabla((X' \cup \{x\}) \oplus Y)= \nabla(X \oplus Y) = \nabla(X) \oplus \nabla(Y) = \nabla(X' \cup\{x\}) \oplus \nabla(Y)$. Argumento análogo vale para $y \in Y$.
Mas se $x \in X$ e $x \in Y$, temos que $x \notin (X \oplus Y)$. Portanto $\nabla(X \oplus Y) \setminus \nabla(\{x\} = (\nabla(X) \oplus \nabla(Y))\setminus\nabla(\{x\})$.
Do lado esquerdo, $\nabla(X\oplus Y)$ já desconsidera $\nabla(\{x\})$ e portanto vale $\nabla(X \oplus Y)$.
Do lado direito temos que $(\nabla(X) \oplus \nabla(Y))\setminus\nabla(\{x\})=(\nabla(X)\setminus\nabla(\{x\}))\oplus(\nabla(Y)\setminus\nabla(\{x\}))$. Assim, as arestas que tem uma ponta em x e outra em $(X\oplus Y)$ não fazem parte do corte, como queríamos demonstrar.
Acho mais fácil mostrar isso diretamente,
sem indução. Basta considerar os vários
tipos de arestas: as que têm uma ponta em
X-Y e outra fora de X \cup Y, as que têm
uma ponta em X-Y e outra em X \cap Y, etc.
Mas se você quer usar indução, também pode.
> Vamos mostrar usando indução em |X| e |Y|.
Não faz muito sentido. A indução deve ser em
|X| ou em |Y| ou em |X|+|Y| ou em |X-Y| etc.
Indução em |X| e |Y| não faz sentido.
> Considere |X|=|Y|=1.
> Se X \cap Y \neq \emptyset, então X=Y,
> . . .
> Considere agora X \cap Y = \emptyset.
> Seja X={x} e Y={y}. Não temos uma aresta
> comum aos dois
Não entendi. O par xy pode ser uma aresta.
> Tome agora |X| > 1, |Y| > 1, X \neq Y.
Êpa! E o caso |X|=1 e |Y|>1?
sem indução. Basta considerar os vários
tipos de arestas: as que têm uma ponta em
X-Y e outra fora de X \cup Y, as que têm
uma ponta em X-Y e outra em X \cap Y, etc.
Mas se você quer usar indução, também pode.
> Vamos mostrar usando indução em |X| e |Y|.
Não faz muito sentido. A indução deve ser em
|X| ou em |Y| ou em |X|+|Y| ou em |X-Y| etc.
Indução em |X| e |Y| não faz sentido.
> Considere |X|=|Y|=1.
> Se X \cap Y \neq \emptyset, então X=Y,
> . . .
> Considere agora X \cap Y = \emptyset.
> Seja X={x} e Y={y}. Não temos uma aresta
> comum aos dois
Não entendi. O par xy pode ser uma aresta.
> Tome agora |X| > 1, |Y| > 1, X \neq Y.
Êpa! E o caso |X|=1 e |Y|>1?
Realmente, professor, acho que compliquei demais nessa prova. E ainda ficou faltando "pontas soltas" (varios detalhes). Percebi depois (e com sua confirmação agora) que nesse caso, indução torna a prova grande e trabalhosa demais.