\documentclass[a4paper]{article}
\pagestyle{empty}
\usepackage{amsmath}
\usepackage[magyar]{babel}
\usepackage[latin2]{inputenc}
\usepackage[mathscr]{eucal}

\newcommand{\jel}[1]{{\bf Jel } {#1} \\}
\newcommand{\defi}[1]{{\bf Def } {#1} \\}
\newcommand{\kov}[1]{{\bf Következmény } {#1} \\}
\newcommand{\tetel}[1]{{\bf Tétel } {#1} \\}
\newcommand{\megj}[1]{{\bf Megjegyzés } {#1} \\}

\newcommand{\Conj}[1]{\overline{#1}}
\newcommand{\Halm}[1]{\mathbbm{#1}}

\newcommand{\V}{\mathbf}
\newcommand{\Hom}{\mathrm{Hom}}
\newcommand{\Lek}[1]{{\cal #1}}
\newcommand{\im}{\mathop{\mathrm{Im}}}
\newcommand{\tr}{\mathop{\mathrm{tr}}}



\frenchspacing
%\addtolength{\textwidth}{2cm}
%\addtolength{\textheight}{6cm}
%\setlength{\hoffset}{-1.3cm}
%\setlength{\voffset}{-3cm}
%\setlength{\parindent}{0pt}

\begin{document}

\begin{center}
{\Large \bf 9. Gyakorlat}
\end{center}

\begin{enumerate}
\item Van-e olyan összefüggő gráf, amelyben:
\begin{enumerate}
\item pontosan egy legolcsóbb él van, és az nem minden 
minimális összsúlyú feszítőfában szerepel;
\item pontosan négy legdrágább él van, és mindegyik szerepel minden minimális összsúlyú fában;
\item pontosan négy legdrágább él van, és a minimális feszítőfák
között van olyan, amelyben mind a négy szerepel, és van olyan is,
amelyben nem mindegyik?
\end{enumerate}

\item Legyenek a gráf $e_1,e_2,\dots$ élei egymástól függetlenül rendre
$p_1,p_2,\dots$ valószínűséggel meghibásodó telefonvonalak. A
kifeszítő fák közül keressük meg azt, amelynek a legnagyobb a
megbízhatósága (tehát amelyre maximális annak a valószínűsége, hogy
egyik él sem hibásodik meg).

\item Hány különböző minimális súlyú feszítőfája van az alábbi
gráfnak:
\vskip 2 cm

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

\vskip 4 cm

\item Mutassuk meg, hogy a Petersen-gráf nem síkbarajzolható!

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

\item (*) Általában milyen lehet?

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

\item Rajzoljuk fel a tórusz felszínére a $K_{3,3}$-at és a $K_5$-öt!

\item (Fáry-tétel) Töröljünk egy-egy élt a $K_{3,3}$ és a
$K_5$-ből. Rajzoljuk le ezeket a gráfokat a síkba úgy, hogy minden
élük egyenes szakasz legyen!

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

\end{enumerate}

\end{document}










