
\problemdata     
{S01-PS4-4}           
{graphs, induction}              
{}              
{F98-PS3, S01-PS4} 		
{S01 Karger}


\begin{problem}

\graphicspath{{/toc/a/class/6.042/spring02/freshRepository/figures/}}

\textbf{Graphs}
Let $G$ and $H$ be undirected graphs with no self-loops.  The {\em
product graph} $P = G \times H$ is defined as follows.  The vertex set
of $P$ is the Cartesian product of the vertex set of $G$ and the
vertex set of $H$.  Thus, each vertex of $P$ is an ordered pair $(v,
w)$ where $v$ is a vertex of $G$ and $w$ is a vertex of $H$.  The
edges in the product graph $P$ are of two types.  First, for every
edge $(v_1, v_2)$ in $G$ and vertex $w$ in $H$, there is an edge
between $(v_1, w)$ and $(v_2, w)$ in $P$.  Second, for every vertex
$v$ in $G$ and edge $(w_1, w_2)$ in $H$, there is an edge between $(v,
w_1)$ and $(v, w_2)$ in $P$.  Note that these two sets of edges are
disjoint.

\begin{problemparts}

\problempart Draw the product of the two graphs shown below.  
Your diagram must be tidy to receive full credit.  In particular,
label all the vertices, e.g., $(b, 3)$, and use two different colors or
line styles (e.g., dashed and solid) to distinguish the two types of
edge defined above.
\begin{center}
\includegraphics[height=1in]{ps3-twographs}
\end{center}


\solution{
  \begin{samepage}
    \begin{center}
      \includegraphics[height=2in]{ps3-product}
    \end{center}
  \end{samepage}
}

\problempart Let $G$ be the graph consisting of two vertices connected
by an edge.  Let $G^n$ be the product of $n$ copies of $G$.  Use
induction to prove that $G^n$ has $2^n$ vertices and $n \cdot 2^{n-1}$
edges.  (You may assume without proof that the $\times$ operation is
associative.)

\solution{
\begin{proof}
The proof is by induction on $n$.  Let $P(n)$ be the proposition that
$G^n$ has $2^n$ vertices and $n 2^{n-1}$ edges.  In the base case,
$P(1)$ is true because $G^1$ has $2^1 = 2$ vertices and $1 \cdot
2^{1-1} = 1$ edge.

In the inductive step, for $n \geq 1$ assume that $G^n$ has $2^n$
vertices and $n 2^{n-1}$ edges to prove that $G^{n+1}$ has $2^{n+1}$
vertices and $(n+1) 2^n$ edges.  The remainder of the argument uses
the fact that $G^{n+1} = G^n \times G$.

The vertex set of $G^{n+1}$ is the Cartesian product of the vertex set
of $G^n$ and the vertex set of $G$.  There are $2^n$ vertices in $G^n$
by induction, and there are 2 vertices in $G$ by the definition of the
graph.  Therefore, there are $2^n \cdot 2 = 2^{n+1}$ vertices in
$G^{n+1}$.

The edges of $G^n \times G$ are of two types.  First, for each edge
$(v_1, v_2)$ in $G^n$ and vertex $w$ in $G$, there is an edge between
$(v_1, w)$ and $(v_2, w)$ in $G^{n+1}$.  Thus, the number of edges of
the first type is equal to the number of edges in $G^n$ multiplied by
the number of vertices in $G$, which gives $n 2^{n-1} \cdot 2 = n
2^n$.

Second, for each vertex $v$ in $G^n$ and edge $(w_1, w_2)$ in $G$,
there is an edge between $(v, w_1)$ and $(v, w_2)$ in $G^{n+1}$.
Thus, the number of edges of the second type is equal to the number of
vertices in $G^n$ multiplied by the number of edges in $G$, which
gives $2^n \cdot 1= 2^n$.  Since these two sets of edges are disjoint,
the total number of edges in $G^{n+1}$ is equal to $n 2^n + 2^n =
(n+1) 2^n$.

This shows that $P(n)$ implies $P(n+1)$, and the claim is proved by
induction.
\end{proof}
}
\end{problemparts}

\end{problem}