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

\usepackage{amsmath}
\usepackage{graphics}

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


\begin{document}

\begin{center}
{\Large \bf Számítástudomány alapjai 2003/2004 tavasz\\
4. gyakorlat: Síkbarajzolhatóság}
\end{center}

\begin{enumerate}

\item Síkbarajzolhatóak-e az alábbi gráfok? Ha igen, rajzoljuk le, ha nem,
bizonyítsuk be.
\begin{figure}[h!]
\begin{center}
\includegraphics{sza04graf1.eps}
\end{center}
\end{figure}

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

\item\label{sumt}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 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.

\item Bizonyítsuk be, hogy egy egyszerű, síkbarajzolható gráfban nem lehet
minden pont foka legalább 6.

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

\item Rajzoljunk néhány önduális gráfot.

\item Adjunk a dualitás segítségével egy másik bizonyítást a 
\ref{sumt}.~feladatban szereplő $t_1+t_2+\dots+t_l=2e$ összefüggésre.


\end{enumerate}
 
\end{document}

