Graf \(\displaystyle{ G}\) jest \(\displaystyle{ 2}\)-spójny \(\displaystyle{ \Leftrightarrow}\) \(\displaystyle{ \forall_{v_1,v_2 \in V\left( G\right) }\exists_{C \subseteq V\left( G\right) }v_1,v_2 \in C}\) , gdzie \(\displaystyle{ C}\) jest cyklem.
Próbuje udowodnić implikację w prawą stronę.
Widzimy, że dla \(\displaystyle{ dist(v_1,v_2)=1}\) zawsze znajdziemy cykl przechodzący przez \(\displaystyle{ v_1,v_2}\)
Przypuśćmy przeciwnie, czyli \(\displaystyle{ \exists_{v_a,v_b}}\) \(\displaystyle{ \neg \left( \exists_{C \subseteq V\left( G\right) }v_a,v_b \in C\right)}\)
Weźmy minimalny kontrprzykład ze względu na \(\displaystyle{ dist\left( v_a,v_b\right)}\) (czyli \(\displaystyle{ dist\left( v_a,v_b\right) \ge 2)}\)
Weźmy najkrótszą drogę prostą \(\displaystyle{ v_a-v_b=\left( v_a,a_1,...,a_k,v_b\right)}\)
\(\displaystyle{ \deg\left( v_a\right) \ge 2}\) , bo \(\displaystyle{ G}\) jest \(\displaystyle{ 2}\)-spójny, więc \(\displaystyle{ \exists_{x \neq a_1}}\) taki, że \(\displaystyle{ v_ax \in E\left( G\right)}\)
Istnieje droga \(\displaystyle{ x-v_b}\) niezawierająca \(\displaystyle{ v_a}\)
Weźmy najkrótszą taką drogę prostą: \(\displaystyle{ \left( x,b_1,...,b_p,v_b\right)}\)
Jeśli byłaby ona rozłączna krawędziowo z \(\displaystyle{ \left( v_a,a_1,...,a_k,v_b\right)}\) to istniałby cykl \(\displaystyle{ \left( v_a,a_1,...,a_k,v_b,b_p,...b_1,x,v_a\right)}\), więc istnieją \(\displaystyle{ i,j}\) takie, że \(\displaystyle{ b_i=a_j}\)
Weźmy najmniejsze takie \(\displaystyle{ i}\) i weźmy drogę: \(\displaystyle{ \left( x,b_1,...b_i,a_{j+1},...,a_k,v_b\right)}\)
Widzimy, że \(\displaystyle{ dist\left( b_i,v_b\right)<dist\left( v_a,v_b\right)}\) , więc istnieje cykl \(\displaystyle{ C_b}\) taki, że \(\displaystyle{ b_i,v_b \in C_b}\) (ale \(\displaystyle{ v_a}\) nie należy do tego cyklu)
Niech \(\displaystyle{ C_1}\) będzie zbiorem krawędzi cyklu \(\displaystyle{ C_b}\) oraz \(\displaystyle{ C_2}\) zbiorem krawędzi cyklu \(\displaystyle{ \left( v_a,x,b_1,..,b_i,a_{j-1},..,a_1,v_a\right)}\)
Weźmy \(\displaystyle{ C_0=C_1\div C_2}\). \(\displaystyle{ C_0}\) jest zbiorem krawędzi cyklu, który zawiera \(\displaystyle{ v_a, v_b}\), czyli otrzymujemy sprzeczność.
Czy ten dowód jest przeprowadzony poprawnie?