\documentclass[12pt]{amsart} 
\usepackage[dvips]{graphics, color}
\theoremstyle{plain}

\newtheorem{theorem}{Theorem}[section]
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}

\theoremstyle{lemma}
\newtheorem{lemma}[theorem]{Lemma}
\theoremstyle{exempel}
\newtheorem{exempel}[theorem]{Exempel}
\theoremstyle{corollary}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{proposition}
\newtheorem{proposition}[theorem]{{Proposition}}
\theoremstyle{clam}
\newtheorem{clam}[theorem]{Claim}
\theoremstyle{conjecture}
\newtheorem{con}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{re}[theorem]{{Remark}}
\newtheorem{no}[theorem]{Notation}



\newtheorem{quest}[theorem]{Question}

\newtheorem{problem}[theorem]{Problem}





\newtheorem{worning}[theorem]{{\rm W\sc orning}}

\newtheorem{para}[theorem]{}

\newtheorem{examp}[theorem]{Example}

\newtheorem{exercise}[theorem]{Exercise}

\newcommand\pn[1]{{\mathbb P}^{#1}}
\newcommand\cal[1]{\mathcal {#1}}
\newcommand\cL{\mathcal L}
\newcommand\cZ{\mathcal Z}
\newcommand\cO[1]{\cal{O}_{\cal{{#1}}}}
\newcommand\X[1]{X^{[{#1}]}}
\newcommand\zed{{\mathbb Z}}
\newcommand\nat{{\mathbb N}}
\newcommand\rat{{\mathbb Q}}
\newcommand\real{{\mathbb R}}
%\newcommand\a{{\aa}}
\textwidth16cm
\textheight20cm
\oddsidemargin-0.3cm
\evensidemargin0.4cm
%\pagestyle{plain} 
\newtheorem{Definition}{\sf Definition}

\title{Lektion 03-29}

\begin{document}
\maketitle

Idag g\aa r vi genom n\aa gra klasser av grafer.

\begin{definition} Grafen $G=(V,E)$ kallas {\bf bipartit} om noderna kan delas upp i tv{\aa} disjunka delar $V=V_1\cup V_2$, $V_1\cap V_2=\emptyset$, s\aa dan 
att varje kant \"ar av formen $ab$ d\"ar $a\in V_1$ och $b\in V_2$.
\end{definition}

 Om varje nod i $V_1$ \"ar f\"orbunda till varje nod i $V_2$ f\aa r vi den {\bf fullst\"andiga} bipartit grafen. Denna betecknas $K_{m,n}$ n\"ar $|V_1|=m$ och $|V_2|=n$.

\vspace{.1in}

\noindent{\it Exempel}. Visa atta alla cykler i en bipartit graf \"ar av j\"amn l\"angt.

L\aa t $\gamma$ vara en cykel som b\"orjar och slutar i $a\in V_1$. M\aa ste f\"orsta och sista kant vara av formen $ab_1, b_na$ d\"ar $b_1, b_2\in V_2$. Cyklen \"ar av formen $ab_1a_1b_2a_2...b_na$ d\"ar $b_i\in V_2$ och $a_i\in V_1$. Vi ser att cyklen har j\"amn l\"angd.
\begin{definition}
En sammanh\"angande graf utam cykler kallas en {\bf tr\"ad}. 
\begin{itemize}
\item Noder med graden $1$ kallas {\bf l\"ov}.
\end{itemize}
\end{definition}

Vi har att:

\vspace{.1in}

\noindent{\it Sats} L\aa t $T=(V,E)$ vara ett tr\"ad, d{\aa}
$$|E|=|V|-1$$

\noindent{Bevis}. Vi ska bevisa det med hj\"alp an induktionen p{\aa} $|V|$.

Om $|V|=1$ vi m\aa ste ha $|E|=0$, d{\aa} \"ar satsen sant.
Antag att satsen g\"aller f\"or varje tr\"ad med $|V|=k$. Vi ska visa at den g\"aller for en tr\"ad med $|V|=k+1$. L\aa t $ab$ vara en kant i $T$. Eftersom det finns bara den h\"ar kanten mellas $a$ och $b$ f\aa r  vi tv{\aa} tr\"ad n\"ar vi tar borta $ab$ fr\aa n $T$. Beteckna dem med $T_1=(V_1,E_1),T_2=(V_2,E_2)$. Enligt induktion $|E_1|=|V_1|-1$ och $|E_2|=|V_2|-1$. Eftersom $|E|=|E_1|+|E_2|+1$ \"ar vi klara.


\vspace{.1in}

\noindent{\it Exempel} Hur m\aa nga icke-isomorfa tr\"ad med $6$ noder finns det?

\begin{definition}
En fraf kallas {\bf plan\"ar} om den (precist ska vi s\"aga n\aa gon geometrisk representation av den) kan ritas i ett plan utan att n\aa gra kanter sk\"ar varandra utanf\"or noderna.
\end{definition}

\noindent Grafer $K_1, K_2, K_3, K_4$ \"ar plan\"ara.\\
Grafen $K_5$ \"ar inte  plan\"ar. 

 L\aa t $G=(V,E)$ vara en sammanh\"angande plan\"ar graf. Antalet delytor beteknar vi med $r$.
Man kan visa att:

\noindent{\it Eulersats}. Det g\"aller att:
$$|V|-|E|+r=2$$

S{\aa} om $K_5$ var  en plan\"ar graf skulle man rita den i planet med $7$ delytor. Den \"ar faktiskt om\"ojligt!

\begin{definition}
En {\bf graff\"argning} \"ar en f\"argning av noder s\aa dan att grannar alltid har olika f\"arg. Den minsta antal f\"arger som beh\"ovs f\"or en graff\"argning kallas den {\bf kromatiska talet} av krafen $G$ och skrives $\chi(G)$.
\end{definition}

En graf kan f{\aa} m\aa nga olika graff\"argningar. Hur m\aa nga?


{\it Exempel} \begin{itemize}
\item Herschels graf.
\item $\chi(G)=1$ om och endast om $G$ best\aa r av isolerade noder, dvs $|E|=0$.
\item Om $G$ \"ar sammanh\"angande och har $n$ noder g\"aller att $2\leq \chi(G)\leq n$.
\item Varje bipartit graf $G$ har $\chi(G)=2$.
\item $\chi(K_n)=n$
\end{itemize}

 Vi definerar $P_G(\lambda)$ som antalet graff\"argningar av grafen $G$ med $\lambda$ stycken f\"arger.

Man kan bevisa at $P_G(\lambda)$ \"ar ett polynom i $\lambda$ och d\"arf\"or kallas det det {\bf kromatiska polynomet}

{\it Exempel} 7.8 i boken.

\section*{\"Ovning}
\begin{enumerate}
\item L\aa t $C_n$ vara en cykel av l\"ancg $n$. Best\"am $n$ om $\chi(G)=2$.
\item Betrakta grafen $K_{n,m}$. Best\"am graden av alla noder.
\item Best\"am n\"ar $K_{n,m}$ eulerisk.
\item Best\"am alla icke-isomorfa tr\"ad med $7$ noder.
\item Visa med hj\"alp av Eulersats att $K_3,3$ \"ar inte plan\"ar.
\end{enumerate}

\end{document}

