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

\setlength\parskip{\medskipamount}
\setlength\parindent{0pt}
\addtolength\textwidth{2.2cm}
\addtolength\hoffset{-1.5cm}
\addtolength\textheight{4.0cm}
\setlength\topmargin{-1.5cm}

\begin{document}

\begin{center}
{\LARGE Bevezetés a számításelméletbe II.}
\\\vspace*{1mm}
3. gyakorlat, 2006. március 1.
\\\vspace*{1mm}
{\footnotesize Koblinger Egmont \texttt{<egmont@cs.bme.hu>}}

\vspace{12mm}
\textbf{\LARGE Menger-tételek, többszörös összefüggőség}
\end{center}

\vspace*{15mm}

\begin{enumerate}
\setcounter{enumi}{21}

%\item Jelöljünk ki egy fában 4 elsőfokú pontot. Mutassuk meg, hogy ezek
%összepárosíthatók úgy, hogy a párok éldiszjunkt utakkal legyenek lefedve!

\item Adjuk meg az $n$ függvényében, hogy hányszorosan összefüggő, illetve
hányszorosan élösszefüggő $K_n$ és $K_{n,n}$.

\item Mutassuk meg, hogy a $k$-szoros pontösszefüggőségből következik a
$k$-szoros élösszefüggőség, de ugyanez visszafelé már nem teljesül.

\item Bizonyítsuk be, hogy ha egy $k$-szorosan összefüggő gráfhoz
hozzáveszünk egy új, legalább $k$ fokú csúcsot, akkor az $k$-szorosan
összefüggő marad.

\item Mutassuk meg, hogy egy $k$-szorosan összefüggő $n$ pontú gráfnak
legalább $\frac{kn}{2}$ éle van.

\item Bizonyítsuk be, hogy ha egy gráf legalább $\frac{n}{2}$-szeresen
összefüggő, akkor van benne Hamilton kör.

\item Mutassunk olyan gráfot, amely kétszeresen összefüggő, háromszorosan
élösszefüggő és legalább négy él megy ki minden pontból.

\item Mutassunk olyan gráfot, amely kétszeresen, de nem háromszorosan
összefüggő, háromszorosan, de nem négyszeresen élösszefüggő és legalább négy
él megy ki minden pontból.

\item Egy gráf akkor és csak akkor 2-szeresen összefüggő, ha bármely két
pontján/élén keresztül vezet kör.

\item Igazoljuk, hogy egy $G(V,E)$ gráf akkor és csak akkor kétszeresen
összefüggő, ha bármely $v \in V$ és $e \in E$-re van olyan kör a gráfban,
mely átmegy $v$-n és $e$-n.

\item Egy $k$-szorosan összefüggő gráfban kijelölünk $k$ darab $A_i$
csúcsot, és $k$ darab $B_j$ csúcsot. Legalább hány közös belső pont nélküli
$A_i-B_j$ út létezik?

\item Legyen $G$ egy kétszeresen összefüggő gráf. Súlyozhatók-e $G$ élei
úgy, hogy nem minden súly egyenlő, viszont $G$ minden feszítőfájának a súlya
azonos legyen?

\item Legyen $k \leq n-1$. Bizonyítsuk be, hogy ha egy $n$ pontú egyszerű
gráfban minden pont foka legalább $\frac{n+k-2}{2}$, akkor a gráf
$k$-szorosan összefüggő.

\item Bizonyítsuk be, hogy 3-reguláris gráfokra az él- és pontösszefüggőségi
számok megegyeznek.

%\item Adott egy $k$-szorosan összefüggő gráf, ennek $2k$ csúcsa $A_1 \ldots
%A_k$ és $B_1 \ldots B_k$. Van-e biztosan $k$ pontfüggetlen út, melynek egyik
%vége az $A$-k, másik vége a $B$-k közül való?

\end{enumerate}

\end{document}
