\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}{0.5 cm}
%\addtolength{\textheight}{6cm}
\setlength{\hoffset}{-0.25cm}
%\setlength{\voffset}{-3cm}
%\setlength{\parindent}{0pt}

\begin{document}

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

\defi {\emph{Erősen összefüggő}nek nevezünk egy irányított gráfot, ha
bármely pont\-já\-ból bármely másik pontba vezet irányított út.}

\defi {Egy irányított gráf egy $v$ pontját \emph{forrás}nak nevezzük, ha
$d_{\textrm{be}}(v)=0$; \emph{nyelő}nek, ha $d_{\textrm{ki}}(v)=0$ }

\defi{\emph{Körmérkőzésgráf}nak nevezzük egy teljes gráf egy
irányítását. (Mindenki mindenkivel játszik pontosan egy mérkőzést, az őket
összekötő élet a győztesből a vesztes felé irányítjuk.)}

\begin{enumerate}

\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 (+4\%) Legyen $G$ egy (véges) 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 Rajzoljunk önduális gráfokat! (Végtelen sokat, ha tudunk!)

\item Rajzoljuk fel a Petersen-gráf duálisát.

\item (+10\%) Bizonyítsuk be, hogy egy élhalmaz akkor és csak akkor
feszítőfa, ha olyan minimális élhalmaz, amely minden vágást
metsz. Bizonyítsuk be, hogy egy élhalmaz akkor és csak akkor
feszítőfa-komplementer, ha olyan minimális élhalmaz, amely minden kört
metsz.

\item Legalább hány éle van egy $n$ pontú erősen összefüggő gráfnak?

\item Bizonyítsuk be, hogy ha egy irányított gráfban nincs irányított
kör, akkor van forrás és nyelő.

\item Bizonyítsuk be, hogy minden körmérkőzés-eredmény esetén van
olyan csapat, amely minden más csapatot vagy legyőzött vagy legyőzte annak
egy legyőzőjét.

\item Bizonyítsuk be, hogy minden körmérkőzés-eredmény esetén sorba
állíthatjuk a résztvevőket úgy, hogy mindenki legyőzte a közvetlenül
utána állót.

\item Igaz-e, hogy ha egy körmérkőzés-gráfban nincs forrás (abszolút
győztes) és nincs nyelő (abszolút vesztes), akkor van Hamilton-kör
($n$ pontú körbeverés)? 

\end{enumerate}

\end{document}










