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

\setlength{\hoffset}{-3 cm}
\setlength{\voffset}{-1 cm}
\addtolength{\textwidth}{5 cm}
\addtolength{\textheight}{8 cm}

\begin{document}

\begin{center}
{\Large \bf 
Számítástudomány elemei\\
3. gyakorlat
}
\end{center}

\large

\begin{enumerate}

\item Legalább hány élet kell hozzáadni a Petersen-gráfhoz, hogy a keletkező gráfban 
legyen Euler-út?

\item Bejárható-e a $4 \times 4$-es ,,sakktábla'' lóval úgy, hogy minden
mezőre pontosan egyszer lépjünk? És az $5 \times 5$-ös? Megoldhatóak-e ezek
úgy, hogy visszaérkezzünk a kiindulási mezőre?

\item Tekintsük az $n \times m$-es négyzethálót, mint gráfot. Van-e ebben
Hamilton út (kör), illetve Euler út (kör)?

\item Igazoljuk, hogy ha egy gráf minden pontjának foka 4, akkor élei színezhetőek 
piros és kék színekkel úgy, hogy minden ponthoz két piros és két kék él illeszkedjék.

\item Bizonyítsuk be, hogy ha egy $n$ pontú egyszerű gráfnak legalább $\binom{n-1}2+2$ 
éle van, akkor van benne Hamilton-kör. Igaz-e ez $\binom{n-1}2+1$ él esetén is?

\item Bizonyítsuk be, hogy a Petersen gráfnak nincs Hamilton köre! És ha elhagyjuk 
valamelyik pontját?

\item Mi lehet egy irányított gráfban az irányított Euler kör létezésének
szükséges és elégséges feltétele? 

\item Bizonyítsuk be hogy tetszőleges összefüggő gráf élei bejárhatóak úgy, hogy 
minden élen mindkét irányban pontosan egyszer megyünk végig!


\item Síkbarajzolhatóak-e az alábbi gráfok?

\begin{center}
\input{sze3sikgrafok.epic}
\end{center}

\item Legyen $G$ egy síkbarajzolható gráf, amelynek $l$ tartománya van
és ezeket rendre $t_1$, $t_2$, $\dots$, $t_l$ él
határolja. Bizonyítsuk be, hogy $t_1+t_2+\dots+t_l=2e$, ahol $e$ az
élek száma.

\item Van egy konvex testünk, amelynek lapjai szabályos öt- és/vagy
hatszögek. Hány ötszöglapja lehet? 

\item Van-e olyan 6, 8, 7 pontú olyan gráf, amelyre sem ő, sem a
komplementere nem síkbarajzolható?

\item Legyen $G$ egy egyszerű összefüggő síkbarajzolható
gráf, amelynek minden tartományát pontosan 6 él határolja. Igazoljuk,
hogy van legfeljebb másodfokú csúcsa. 
%(Útmutatás: próbálkozzunk indirekt bizonyítással!)

\item Bizonyítsuk be, hogy egyszerű páros síkgráf duálisában van
Euler-kör.

\item Bizonyítsuk be, hogy egy egyszerű páros 4-reguláris gráf nem
síkbarajzolható.

\end{enumerate}
 
\end{document}
