\documentclass[a4paper]{article}
\pagestyle{empty}
\usepackage[T1]{fontenc}
\usepackage[latin2]{inputenc}
\usepackage[magyar]{babel}

\usepackage{amsmath}
\usepackage{amssymb}

%\usepackage{fullpage}
%\addtolength{\textheight}{2 cm}


\begin{document}
\begin{center}
{\Large \bf Számítástudomány alapjai 2003/2004 tavasz\\
6.~hét: Gyakorlás}
\end{center}

\begin{enumerate}

\item $4n$ játékos $n$ asztalnál bridzselni akar. Minden játékoshoz
kell egy másik, aki a partnere lesz, és minden partnerből álló párhoz
kell egy másik pár, akik az ellenfeleik lesznek. Hány lehetőség van a
partnerek és ellenfelek kiválasztására?

\item Legyen $G$ a következő gráf. $G$ pontjai az $\{1,2,3,4,5 \}$
halmaz háromelemű részhalmazai. Két ilyen halmaz között vezet él,
ha metszetük pontosan egy elemű. Egy él súlya az a szám, amely 
végpontjainak közös eleme. Hány minimális összsúlyú feszítőfája 
van $G$-nek?

\item Van-e Euler út és kör abban a $G$ gráfban, aminek pontjai az 
1,2,\dots100 számok, és $(a,b)\in E(G)$ pontosan akkor, ha $|a-b|\le2$
és $a\neq b$.

\item Bizonyítsuk be, hogy egy egyszerű összefüggő gráf pontosan akkor fa, 
ha minden szélességi bejárása ugyanazt a gráfot adja.

\item Egy $G=(A,B)$ páros gráfban létezik olyan $X\subseteq A$
ponthalmaz, amelyre $|N(X)| \leq |X|-2$. Bizonyítsuk be, hogy a
gráfban nincs Hamilton-út.


\end{enumerate}
 
\end{document}

