1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
\input ws-form.tex
\input tikz%graphs
{\bf \noindent\line{Math 3012-QHS \hfil Name: \rm \underline{Holden Rohrer}}
Fall 2019\par\noindent
Worksheet 2\par\noindent
Due 09/10/2019}
\smallskip \hrule \medskip
\def\G{{\bf G}}
\question{%
Q1 - (Chapter 5, Exercise 18) Find a proper $(t+1)$-coloring of the graph $\G_{t+1}$ in Mycielski's proof of Proposition 5.25. This establishes that $\chi(\G_{t+1})\leq t+1$.
}{
$\G_{t+1}=(V,E)$ is constructed as a $t$-colorable graph $\G_t$, an independent graph $I$ where $|I|=|G_t|=n$, and a separate vertex $z$. For the distinct vertices $i_1,i_2,\dots,i_n \in I$, $\{i_k,z\} \in E$ and $\{i_k,g_{G_j}\} \in E$ if $\{G_{t_j},G_{t_i}\} \in E$, given a similar enumeration on $G$.
Let $\phi:V\to C$ be a proper coloring where $C$ is a set of colors $|C|=t+1$. If $\phi(i_k)=\phi(G_{t_j})$ and $\phi(z)=c$ where $c \notin \phi(I)$, $\phi$ is a proper coloring of $G_{t+1}$ on $t+1$ colors.
}
\question{%
Q2 - (Chapter 5, Exercise 20) Construct and draw the graph $\G_5$ from Mycielski's proof of Proposition 5.25.
}{
\tikzpicture
\node[draw,circle,inner sep=0.1cm,fill=white] (a) at (0,0) {};
\node[draw,circle,inner sep=0.1cm,fill=white] (b) at (0,1) {};
\node[draw,circle,inner sep=0.1cm,fill=white] (c) at (1,0) {};
\node[draw,circle,inner sep=0.1cm,fill=white] (d) at (2,0) {};
\node[draw,circle,inner sep=0.1cm,fill=white] (e) at (1,1) {};
\node[draw,circle,inner sep=0.1cm,fill=white] (f) at (0,2) {};
\node[draw,circle,inner sep=0.1cm,fill=white] (g) at (3,0) {};
\node[draw,circle,inner sep=0.1cm,fill=white] (h) at (2,1) {};
\node[draw,circle,inner sep=0.1cm,fill=white] (i) at (1,2) {};
\node[draw,circle,inner sep=0.1cm,fill=white] (j) at (0,3) {};
\node[draw,circle,inner sep=0.1cm,fill=white] (k) at (4,0) {};
\node[draw,circle,inner sep=0.1cm,fill=white] (l) at (3,1) {};
\node[draw,circle,inner sep=0.1cm,fill=white] (m) at (2,2) {};
\node[draw,circle,inner sep=0.1cm,fill=white] (n) at (1,3) {};
\node[draw,circle,inner sep=0.1cm,fill=white] (o) at (0,4) {};
\node[draw,circle,inner sep=0.1cm,fill=white] (p) at (5,0) {};
\node[draw,circle,inner sep=0.1cm,fill=white] (q) at (4,1) {};
\node[draw,circle,inner sep=0.1cm,fill=white] (r) at (3,2) {};
\node[draw,circle,inner sep=0.1cm,fill=white] (s) at (2,3) {};
\node[draw,circle,inner sep=0.1cm,fill=white] (t) at (1,4) {};
\node[draw,circle,inner sep=0.1cm,fill=white] (u) at (0,5) {};
\node[draw,circle,inner sep=0.1cm,fill=white] (v) at (6,0) {};
\node[draw,circle,inner sep=0.1cm,fill=white] (w) at (5,1) {};
\draw (a) -- (b) -- (c) -- (d) -- (e) -- (a);
\draw (a) -- (f) -- (c);
\draw (b) -- (g) -- (d);
\draw (c) -- (h) -- (e);
\draw (d) -- (i) -- (a);
\draw (e) -- (j) -- (b);
\draw (f) -- (k); \draw (g) -- (k); \draw (h) -- (k); \draw (i) -- (k); \draw (j) -- (k); %G_4
\draw (a);
\endtikzpicture
Starting with $C_5$, I constructed $G_4$ and then $G_5$ outwards from the origin.
AAAAAAAHHHHHHH. I have decided to complete this on paper.
}
\question{%
Q3 - (Chapter 5, Exercise 31) Exhibit a planar drawing of an eulerian planar graph with 10 vertices and 21 edges.
}{
}
\question{%
Q4 - (Chapter 5, Exercise 32) Show that every planar graph has a vertex that is incident to at most five edges.
}{}
\bye
|
