\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{-1.5cm}
\addtolength\textwidth{4.8cm}
\addtolength\hoffset{-0.5cm}
\addtolength\textheight{5.5cm}
\setlength\tabcolsep{2pt}
\setlength\arraycolsep{2pt}

\usepackage{amssymb}
\usepackage{graphicx}

\begin{document}

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

\vspace{10mm}
\textbf{\LARGE Gráfszínezések 1.}
\end{center}

\vspace*{9mm}

\begin{enumerate}
\setcounter{enumi}{15}

\item Bizonyítsuk be, hogy ha egy páros gráf minden csúcsának fokszáma 4,
akkor van benne olyan kör, melynek hossza legalább 8.

%\item Igazoljuk, hogy $\chi(G)\geqslant {|V(G)|\over \alpha(G)}$.
%Keressünk olyan gráfokat, ahol ez a becslés pontos, illetve ahol
%pontatlan. 

\item Hány szín szükséges az alábbi gráf pontjainak kiszínezéséhez?

\begin{figure}[h!]
\begin{center}
\scalebox{1}{\includegraphics{4szin.eps}}
\end{center}
\end{figure}
\vspace{-1.5 \baselineskip}

\item Legyen $V(G)=\{v_1,\dots,v_{100}\}$, ahol $v_i$ és $v_j$ között akkor és
csak akkor megy él, ha $7\geq |i-j|$. Mennyi $G$ kromatikus száma?

\item Legyenek $G$ csúcsai az összes természetes számok és legyen 
az $n$ és $m$ csúcs éllel összekötve pontosan akkor, ha $n+m$
páratlan. Mennyi a gráf kromatikus száma?

\item A $V(G)={1, 2, \ldots 1023}$ ponthalmazon definiáljuk a $G$ gráfot
úgy, hogy benne $k$ és $m$ pontosan akkor van összekötve éllel, ha nem
egyenlőek és az egyik osztja a másikat. Határozzuk meg $\chi(G)$ értékét.
  
\item Bizonyítsuk be, hogy minden $n$ csúcsú gráfra
$\chi(G)\cdot\chi(\overline{G}) \geqslant n$.

\item Bizonyítsuk be, hogy minden páros $G$ gráfra $\chi(G)=\omega(G)$.

\item Bizonyítsuk be, hogy tetszőleges egyszerű gráfra $|E(G)|\geq {\chi(G)\choose
2}$.

\item Igaz-e, hogy minden egyszerű $G$ gráfnak van olyan $\chi(G)$ színnel
való színezése, melyben az egyik színosztály $\alpha(G)$ csúcsot tartalmaz?
($\alpha$: független pontok maximális száma.)

\item Mutassuk meg, hogy ha $G_1$ és $G_2$ két gráf ugyanazon a $V$
csúcshalmazon, $G$ pedig a szintén ezen a csúcshalmazon definiált, $G_1$ és
$G_2$ éleinek unióját tartalmazó gráf, akkor $\chi(G)\leq
\chi(G_1)\chi(G_2)$.

\item Legyen adva a síkon véges sok egyenes, melyek közül semelyik három sem
metszi egymást egy pontban. Legyenek a $G$ gráf csúcsai a metszéspontok,
élei pedig az egyes egyeneseken a szomszédos csúcspárok közötti szakaszok.
Bizonyítandó, hogy $\chi(G)\leq 3$.

\end{enumerate}

\end{document}
