From 56b740565fd6467564be28b5465ad24cccf71109 Mon Sep 17 00:00:00 2001 From: Holden Rohrer Date: Thu, 16 Jan 2020 21:24:46 -0500 Subject: moved comb hw --- tech-math/comb/ws3.tex | 64 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 64 insertions(+) create mode 100644 tech-math/comb/ws3.tex (limited to 'tech-math/comb/ws3.tex') 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 -- cgit