\documentclass[a4paper]{article}
\usepackage{t1enc}
\usepackage[utf8]{inputenc}
\usepackage[magyar]{babel}
\frenchspacing
\sloppy
\pagestyle{empty}

\setlength\marginparsep{0cm}
\setlength\oddsidemargin{0cm}
\setlength\evensidemargin{0cm}
\setlength\topmargin{-2.5cm}
\addtolength\textwidth{5.8cm}
\addtolength\hoffset{-1.2cm}
\addtolength\textheight{5.5cm}
\setlength\tabcolsep{2pt}
\setlength\arraycolsep{2pt}

\usepackage{graphicx}
%\usepackage{epic}

\begin{document}

\begin{center}
{\LARGE Bevezetés a számításelméletbe I.}
\\\vspace*{1mm}
12. gyakorlat, 2005. december 5.
\\\vspace*{1mm}
{\footnotesize Koblinger Egmont \texttt{<egmont@cs.bme.hu>}}

\vspace{8mm}
\textbf{\LARGE Gráfok – Síkbarajzolhatóság}
\end{center}

\vspace*{9mm}

\begin{enumerate}
\setcounter{enumi}{140}

\item Síkbarajzolhatóak-e az ábrán látható gráfok?
\vspace*{-0.4cm}
\begin{figure}[h]
  \begin{center}
\input{muab14.pstex_t}
%\input{muab4.pstex_t}
\end{center}
\end{figure}
\vspace*{-0.5cm}

\item Négy szomszéd mindegyike úgy épített utat a másik három házához,
hogy azok nem keresztezik egymást. Egy ötödik ember újabb házat épít.
\begin{itemize}
\item Bizbe, hogy nem tud úgy utakat építeni házától a másik
négy házához, hogy az úthálózatban ne legyenek kereszteződések.
\item Bizbe, hogy valamely három házhoz viszont tud kereszteződés
nélkül utat építeni.
\end{itemize}

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

\item Keressünk olyan 8 pontú gráfot, hogy se ő, se a komplementere ne
legyen síkbarajzolható.

\item Keressük meg az összes 6 csúcsú nem síkgráfot.

\item Hány metszéspontja van maximálisan egy konvex 9-szög átlóinak?

\item Mutassuk meg, hogy egy nyolc csúcsú teljes gráfot a síkra
lerajzolva legalább 10 élkeresztezés jön létre.

\item Egy 20 csúcsú konvex poliéder lapjainak száma 12. Hány oldala van
az egyes lapoknak, ha tudjuk, hogy ez a szám minden lapra azonos? 

\item Egy hatelemű halmaz részhalmazai legyenek egy gráf pontjai.
Két pont akkor legyen összekötve éllel, ha a nekik megfelelő
részhalmazok diszjunktak (metszetük üres). Síkbarajzolható-e ez a
gráf?

\item Tudjuk, hogy síkbarajzolható gráfok esetén $n+t=e+2$. Hogyan módosul
ez a képlet nem síkbarajzolható gráfok esetén?

\end{enumerate}

\end{document}
