\documentclass[12pt]{article}
\textwidth = 6.7 in
\textheight = 9.2 in
\oddsidemargin = 0.0 in
\evensidemargin = 0.0 in
\topmargin = 0.2 in
\headheight = 0.0 in
\headsep = 0.0 in
\parskip = 0.2in
\parindent = 0.0in

\usepackage{amsmath,amssymb,enumerate,gastex}
%\def\rmdefault{bch} % Use Charter for main text font.

% =========================================================
\begin{document}

\begin{center}
{\LARGE
\textbf{CS 173: Discrete Structures, Fall 2009}
\\
\textbf{Homework 11}
\\[1ex]}
\end{center}

This homework contains 5 problems worth a total of 48 points.
It is due on Wednesday, December 9th at noon.   Put your homework in
the appropriate dropbox in the Siebel basement.



\begin{enumerate}

%----------------------------------------------------------------------
\item 
\textbf{Equivalence relations [8 points]}

Let's define the relation $\sim$ on $\mathbb{R}$ such that $x \sim y$ if
and only if $x-y \in \mathbb{Z}$.   

\begin{itemize}
\item List three elements of $[1.3]$.   Give a precise set-builder description
of what's in $[1.3]$.
\item How many equivalence classes does $\sim$ have?
\item Prove that $\sim$ is an equivalence relation.
\end{itemize}

%----------------------------------------------------------------------
\item 
\textbf{Partial orders [8 points]}

In your mind, picture $\mathbb{R}^2$ as the set of (open) intervals of the real line.
Let's define a relation $\ll$ on $\mathbb{R}^2$ as follows.  
Intuitively, 
$(a,b)\ll (c,d)$ if the two intervals overlap with $(a,b)$ starting no later than $(c,d)$.
Formally:

\begin{quote}
$(a,b) \ll (c,d)$ if and only if $a \le c$ and $c < b \le d$
\end{quote}

\begin{itemize}
\item Prove that $\ll$ is antisymmetric.
\item Prove that $\ll$ is not a partial order, using a concrete counter-example to
show that it lacks one of the properties required to be a partial order.
\end{itemize}


%----------------------------------------------------------------------
\item 
\textbf{Showing an operation is well-defined [10 points]}

Let's define a relation $\sim$ on $\mathbb{R}^2 - \{(0,0)\}$ by 

\begin{quote}
$(x,y) \sim (p,q)$ if and only if $(x,y) = (\lambda p, \lambda q)$
for some positive real number $\lambda$
\end{quote}

Then define an addition operation on the equivalence classes of this
relation:

$$[(x,y)] + [(p,q)] = [(xp-yq,xq + yp)]$$

\begin{enumerate}
\item Each equivalence class is a familiar geometrical object.   Which
one?   Give a geometrical description of what this addition operation does.
\item Prove that this addition operation is well-defined.   That is,
show that, if you pick different representatives for the two input equivalence
classes, the output value still lives in the same equivalence class.
\end{enumerate}


\newpage
%----------------------------------------------------------------------
\item 
\textbf{Graphs and recursion [12 points]}

Let's define a new set of graphs $X_n$ as follows:

\begin{itemize}
\item $X_1$ consists of two vertices and no edges.
\item For every $k \ge 2$, $X_k$ consists of a copy of $X_{k-1}$
plus two additional vertices.   There is an edge from each of the
additional vertices to each vertex in the copy of $X_{k-1}$.

\end{itemize}

For example, the following figure shows $X_1$, $X_2$, $X_3$, and $X_4$.
A star marks the vertices in the copy of $X_{k-1}$.

    \begin{picture}(120,40)(0,-40)
%        \gasset{Nframe=n}  %no border around nodes
        \gasset{AHnb=0} % no arrowheads
        \gasset{Nadjust=wh} %match width to label


        \node(x1a)(10.0,-10.0){}
        \node(x1b)(10.0,-30.0){}

        \node(x2a)(40.0,-10.0){$\star$}
        \node(x2b)(40.0,-30.0){$\star$}
        \node(x2c)(30.0,-20.0){}
        \node(x2d)(50.0,-20.0){}

	\drawedge(x2c,x2a){}
	\drawedge(x2c,x2b){}
	\drawedge(x2d,x2a){}
	\drawedge(x2d,x2b){}

        \node(x3a)(80.0,-10.0){$\star$}
        \node(x3b)(80.0,-30.0){$\star$}
        \node(x3c)(70.0,-20.0){$\star$}
        \node(x3d)(90.0,-20.0){$\star$}
	\node(x3e)(65,-5.0){}
	\node(x3f)(95,-35.0){}

	\drawedge(x3c,x3a){}
	\drawedge(x3c,x3b){}
	\drawedge(x3d,x3a){}
	\drawedge(x3d,x3b){}
	\drawedge(x3e,x3a){}
	\drawedge(x3e,x3b){}
	\drawedge(x3e,x3c){}
	\drawedge(x3e,x3d){}
	\drawedge(x3f,x3a){}
	\drawedge(x3f,x3b){}
	\drawedge(x3f,x3c){}
	\drawedge(x3f,x3d){}


        \node(x4a)(125.0,-10.0){$\star$}
        \node(x4b)(125.0,-30.0){$\star$}
        \node(x4c)(115.0,-20.0){$\star$}
        \node(x4d)(135.0,-20.0){$\star$}
	\node(x4e)(110,-5.0){$\star$}
	\node(x4f)(140,-35.0){$\star$}
	\node(x4g)(110,-35.0){}
	\node(x4h)(140,-5.0){}

	\drawedge(x4c,x4a){}
	\drawedge(x4c,x4b){}
	\drawedge(x4d,x4a){}
	\drawedge(x4d,x4b){}
	\drawedge(x4e,x4a){}
	\drawedge(x4e,x4b){}
	\drawedge(x4e,x4c){}
	\drawedge(x4e,x4d){}
	\drawedge(x4f,x4a){}
	\drawedge(x4f,x4b){}
	\drawedge(x4f,x4c){}
	\drawedge(x4f,x4d){}

	\drawedge(x4g,x4a){}
	\drawedge(x4g,x4b){}
	\drawedge(x4g,x4c){}
	\drawedge(x4g,x4d){}
	\drawedge(x4g,x4e){}
	\drawedge(x4g,x4f){}

	\drawedge(x4h,x4a){}
	\drawedge(x4h,x4b){}
	\drawedge(x4h,x4c){}
	\drawedge(x4h,x4d){}
	\drawedge(x4h,x4e){}
	\drawedge(x4h,x4f){}


    \end{picture}


Suppose that $V_k$ and $E_k$ are the number of vertices and edges in $X_k$.

\begin{enumerate}
\item Give a table showing the number of vertices and the number of edges in
$X_k$, for $k$ from 1 through 6.
\item Give a formula for $V_k$.
\item Write a recurrence (with base case) for $E_k$.   
\item Solve the recurrence to get a closed-form expression for $E_k$.
\item The distance between two vertices $a$ and $b$
is the number of edges on the shortest path from $a$ to $b$ (which is zero if
$a = b$).
The diameter of a connected graph is the maximum distance between any two 
vertices.   For $k \ge 2$, what is the diameter of $X_k$?   Briefly explain why
your answer is correct.
\end{enumerate}

%----------------------------------------------------------------------
\item 
\textbf{Planar graphs [10 points]}

See problem 1 for the definition of the graph $X_k$.   Also notice that this
depends on material which will be presented in lecture Friday.

\begin{enumerate}
\item Show that $X_3$ is planar by redrawing it so that 
pairs of edges never cross.
\item We will see in class (but perhaps not before you've started work on
this homework) that a graph cannot be planar if it contains $K_{3,3}$ or $K_5$ as a subgraph.   
Show that $X_4$ is not planar by showing that it has a subgraph that is isomorphic
to one of these 
two special graphs.  The most effective way to do this is probably
a combination of a labelled picture (start with what you did for part a)
combined with some explanation.
\item Suppose that $G$ is an undirected connected simple planar graph with
8 vertices, 2 of which have degree 4 and 6 of which have degree 3.   How
many edges does it have?   How many regions does it have?  (Hint:  use Euler's
formula.)
\end{enumerate}



\end{enumerate}

\end{document}
