\input /home/pasky/school/fastex/lib.tex

\subchapter{V�ta o sudosti (princip sudosti)}{

	$$ \forall G = (V,E):\ \sum_{v\in V} \deg_{G}(v) = 2|E| $$

\proof{
	Vlevo ka�d� hrana p�isp�je $2\times$.
	\qed
}

\scpart{D�sledek:}{
	$\forall G$: po�et vrchol� lich�ho stupn� je sud�.
}

\note{
	Neplat� pro nekone�n� grafy ({\tt o-o-o-o-$\cdots$}).
}

}


\asciiart{
    o
  /   \
o ----- o ----- o ----- o
}


\subchapter{Sk�re grafu}{

	$$ G = (\{v_{1}, \ldots, v_{n}\}, E), \textbox{\bf sk�re grafu G} = D(G) = (\deg_{G}(v_{1}), \ldots, \deg_{G}(v_{n})) $$

	Dv� sk�re pova�ujeme za stejn�, pokud se li�� pouze po�ad�m prvk�.

\scpart{P��klad:}{

	\asciiart{
    o
  /   \
o ----- o ----- o ----- o
}
	m� sk�re $(1,2,2,2,3)$.

	\asciiart{
    o
  /   \
o - o - o - o
}
	k n�mu nen� izomorfn�.
}

\scpart{V�ta o sk�re:}{

	$$ D = (d_{1}, \ldots, d_{n},\ 0 \le d_{1} \le \cdots \le d_{n}) $$

	$D$ je sk�re n�jak�ho grafu, pr�v� kdy�
	$$D'=(d_{1}, \ldots, d_{n-d_{n}-1}, d_{n-d_{n}} - 1, \ldots, d_{n-2}-1, d_{n-1}-1)$$
	je sk�re n�jak�ho grafu.

\scpart{P��klady pou�it�:}{
	Je $(1,2,3,3,3,4,4)$ sk�re n�jak�ho grafu?

	$(1,2,2,2,2,3)$ sk�re n�jak�ho grafu?

	$$(1,2,1,1,1)$$
	$$(1,1,1,1,2)$$
	$$(1,1,0,0) \Leftrightarrow (0,0,1,1)$$
	$$(0,0,0)$$\nobreak je sk�re grafu.

	Je $(1,1,1,2)$?
	$$(1,0,0)$$
	$$(0,0,1)$$
	$$(0,-1)$$\nobreak nen�.

	Je $(0,1,2,3,4,4)$?
	$$(0,0,1,2,3)$$
	$$(0,-1,0,1)$$
}

\proof{
	\proofleftimpl{

	$G'$ m� sk�re $D'$. P�id�me ke $G'$ nov� vrchol $v_{n}$ a spoj�me ho
	hranou s vrcholy $v_{n-1}$, $v_{n-2}$, $\ldots$, $v_{n-d_{n}}$. Dost�v�me tak
	graf se sk�re $D$.

	}


	\proofrightimpl{

	P�edpokl�d�me, �e $G=(\{v_{1}, \ldots, v_{n}\}, E)$ m� sk�re $D$.
	Ozna�me $d = d_{n} = \deg v_{n}$.

	{\bf Prvn� p��pad:} Z $v_{n}$ vedou hrany do vrchol� $v_{n-1},v_{n-2},\ldots,v_{n-d}$.
	Odstran�n�m $v_{n}$ pak z t�chto hran dostaneme graf se sk�re $D'$.

	{\bf Druh� p��pad:} Neplat� prvn� p��pad, tedy potom je vrchol $v_{n}$ propojen
	s jin�mi vrcholy, ne� je posledn�ch $d_{n}$, neboli:
	$$ i < n-d \le j:\ \{v_{i}, v_{n}\} \in E,\ \{v_{j}, v_{n}\} \nin E $$

	Ale proto�e $\deg v_{i}$ $(= d_{i})$ $\le \deg v_{j}$ $(= d_{j})$, existuje
	$v_{k}$ $(k \not= i,j)$ takov�, �e $\{v_j, v_k\} \in E$, $\{v_i, v_k\} \nin E$
	(tedy existuje zase n�jak� vrchol $v_k$ takov�, kter� je spojen� s $v_j$,
	ale ne $v_k$ a t�m se stupe� kompenzuje).

	P�id�me do $E$ hrany $\{v_i,v_k\}, \{v_j, v_n\}$, odebereme z $E$ hrany
	$\{v_i, v_n\}, \{v_j, v_k\}$. Sk�re tak z�st�v� $D$, ale zmizela neposedn�
	hrana mimo posledn�ch $d_n$ prvk� (vrcholy $v_i, v_j$ jsme m�sto p�es $v_n$
	spojili p�es $v_k$). P�evedli jsme tedy situaci na prvn� p��pad.

	}

	\qed

}

}

}

\bend
