moved comb hw

1 files changed, 64 insertions, 0 deletions

diff --git a/tech-math/comb/ws3.tex b/tech-math/comb/ws3.tex
new file mode 100644
index 0000000..841c9a9
--- /dev/null
+++ b/tech-math/comb/ws3.tex
@@ -0,0 +1,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