\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}
\begin{document}
{\sf KTH Matematik}
\begin{center} 
 {\bf  5B1118 Diskret Matematik \\
L\"osningar till Kontrollskrivning 3 \\
Fredagen den 1 22 Mars, 2004 \\}
\end{center}

\vspace{.3in}


\begin{enumerate}
\item  L\aa t $G=(V,E)$ vara en enkel graf.
\begin{itemize}
\item Best\"am $|V|$ om $|E|=9$ och varje nod har grad $3$.

L\aa t $|V|=n$. Vi har att:
$$\sum_{v\in V}deg(v)=3n=2|E|=18$$
S{\aa} $n=6$.
\item Ger en geometrisk representation av $G$, dvs rita grafen $G$.

\setlength{\unitlength}{1.5cm}
\begin{picture}(2.5,1.5)
\put(0,0){\circle*{0.1}}
\put(1,0){\circle*{0.1}}
\put(2,0){\circle*{0.1}}
\put(1,1){\circle*{0.1}}
\put(0,1){\circle*{0.1}}
\put(2,1){\circle*{0.1}}
\put(0,0){\line(1,0){2}}
\put(0,0){\line(0,1){1}}
\put(0,0){\line(2,1){2}}
\put(2,0){\line(0,1){1}}
\put(2,0){\line(-2,1){2}}
\put(2,1){\line(-2,0){2}}
\put(1,1){\line(0,-1){1}}
\end{picture}

\item \"Ar $G$ en eulersk graf?(Motivera ditt svar)

$G$ \"ar sammangande. Eftersom alla noder har odd grad kan $G$ inte vara en eulerskgraf.
\end{itemize}
\item  Avg\"or om dessa grafer \"ar isomorfa.(Motivera ditt svar).

 $G_1=$\setlength{\unitlength}{1cm}
\begin{picture}(3,2.2) 
\put(2,0){\circle*{0.1}}
\put(0,2){\circle*{0.1}}
\put(0,0){\circle*{0.1}}
\put(2,2){\circle*{0.1}}
\put(1,1){\circle*{0.1}}
\put(0,0){\line(1,0){2}}
\put(0,0){\line(0,1){2}}
\put(0,0){\line(1,1){2}}
\put(2,0){\line(0,1){2}}
\put(2,0){\line(-1,1){2}}
\put(0,2){\line(1,0){2}}
\end{picture}
$G_2$= \begin{picture}(3,2.2)
\put(2,0){\circle*{0.1}}
\put(0,2){\circle*{0.1}}
\put(0,0){\circle*{0.1}}
\put(2,2){\circle*{0.1}}
\put(3,1){\circle*{0.1}}
\put(0,0){\line(1,0){2}}
\put(0,0){\line(0,1){2}}
\put(0,0){\line(3,1){3}}
\put(2,0){\line(-1,1){2}}
\put(2,2){\line(-1,-1){2}}
\put(0,2){\line(3,-1){3}}
\put(2,0){\line(1,1){1}}
\put(2,2){\line(1,-1){1}}
\end{picture}

Tv{\aa} isomorfa grafer m\aa ste ha motsvarande noder av samma graed.

Efter ger man en ordning till noder i $G_1$ pch $G_2$ kan man skriva sekvensen av grader i $G_1$, $\gamma_{G_1}$, och sekvensen av grader i $G_2$, $\gamma_{G_1}$:
$$\gamma_{G_1}=(3,3,3,3,4)$$
$$\gamma_{G_2}=(2,3,3,4,4)$$

Det visar att $G_1$ och $G_2$  inte \"ar isomorfa.

\item \begin{itemize} \item Rita en graf med incidensmatris:
\[ A_G=\left( \begin{array}{ccccc}
1&0&0&0&0\\
0&1&1&0&0\\
0&0&1&1&0\\
0&0&0&1&1\\
1&1&0&0&1
\end{array} \right)\]

$G$ har $5$ noder, $v_1,v_2,...,v_5$ av grad $(1,2,2,2,3)$, och $5$ kanter.
Enligt matrisen har vi:

\setlength{\unitlength}{1.5cm}
\begin{picture}(2.5,1.5)
\put(1,0){\circle*{0.1}}
\put(2,0){\circle*{0.1}}
\put(1,1){\circle*{0.1}}
\put(0,1){\circle*{0.1}}
\put(2,1){\circle*{0.1}}
\put(2,0){\line(0,1){1}}
\put(1,1){\line(0,-1){1}}
\put(1,0){\line(0,1){1}}
\put(1,0){\line(1,0){1}}
\put(0,1){\line(1,0){1}}
\put(1,1){\line(1,0){1}}

\end{picture}



\item \"Ar $G$ en tr\"ad? (Motivera ditt svaret.)

 $G$ inneh\aa ller en cykel (av l\"angd $4$) d{\aa} inte \"ar en tr\"ad.
\item Best\"am $\chi(G)$.

For varje graf \"ar $\chi(G)\geq 2$.
Man kan ha en graff\"argning av $G$ med 2 f\"arger A,B:

\setlength{\unitlength}{1.5cm}
\begin{picture}(2.5,1.7)

\put(1,0){\circle*{0.1}}
\put(.8,0){A}
\put(2,0){\circle*{0.1}}
\put(2.1,0){B}
\put(1,1){\circle*{0.1}}
\put(1,1.1){B}
\put(0,1){\circle*{0.1}}
\put(0,1.1){A}
\put(2,1){\circle*{0.1}}
\put(2.1,1){A}
\put(2,0){\line(0,1){1}}
\put(1,1){\line(0,-1){1}}
\put(1,0){\line(0,1){1}}
\put(1,0){\line(1,0){1}}
\put(0,1){\line(1,0){1}}
\put(1,1){\line(1,0){1}}
\end{picture}

d{\aa} \"ar $\chi(G)=2$.
\end{itemize}
\end{enumerate}

\end{document}