grafos:provadecomarvprop1 [WikiMat]

Essa página está em modo somente de leitura. Você pode visualizar a fonte, mas não alterá-la. Informe-se com o administrador do Wiki, caso você ache que isso está incorreto.

**Definição 1 \(\implies\) Definição 2:**

\(\text{a}_2\)) \(v \in V_t \implies  y \in T_v\) para algum \(t\)
  * Por \(\text{a}_1\)) todo vértice esta em algum saco, portanto \(v \in V_t\) para todo \(v \in G\) e para algum \(t\)
  * Para notar que cada \(T_v\) é conexo é simples, tome \(t_1, t_2 \in T_v\) na árvore \(T\) existe um único caminho que conecta eles
  * Basta então usar \(\text{c}_1\)), pois existe \(t_3 \in t_1 T t_2\) e portanto \(v_{t_1} \cap V_{t_2} \subset V_{t_3}\), assim \(t_3 \in T_v\)

\(\text{b}_2\)) Dado aresta \(xy\) ela pertence a algum \(V_t\) e portanto \(t \in T_x \cap T_y\) 


**Definição 2 \(\implies\) Definição 1:**

\(\text{a}_1\)) Se \(t \in T_v \implies v \in V_t\), obvio pois \(T_v \subset T\) é subárvore por definição

\(\text{b}_1\)) Se existe aresta \(xy\) por hipótese \(t \in T_x \cap T_y \implies xy \in V_t\), com isso achamos inclusive a qual saco que a interseção pertence

\(\text{c}_1\)) Seja \(v \in V_a \cap V_c\) e \(b \in aTc\)
  * \(a,c \in T_v\), pois \(v \in V_a,V_c\), portanto \(b \in T_v\), pois \(T_v \subset T\) é subárvore
  * Agora vamos supor por absurdo que existe \(x \in V_a \cap V_c\) tal que \(x \notin V_b\), ou seja, \(b \notin T_x\)
  * Tal fato é impossível, pois como \(T\) é uma árvore e \(b \in aTc\) o único caminho possível é com \(b \in T_x\), pois caso contrário, \(T_x\) seria desconexo