pset1/fall99.tex:\usepackage{graphics}
pset1/fall99sol.tex:\usepackage{graphics}
pset1/spring99.tex:\cap B}$.  \hint See \S1.5, paragraph following Example 5.
pset1/spring99sol.tex:\usepackage{graphics}
pset1/spring99sol.tex:paragraph, let's introduce four boolean variables.
pset1/spring99sol.tex:Now we can translate the paragraph into logic notation as follows.
pset10/fall98sol.tex:\usepackage{graphics}
pset10/fall99.tex:\usepackage{graphics}
pset10/fall99.tex:\centerline{\resizebox{!}{3in}{\includegraphics{H64-tennis.eps}}}
pset10/fall99.tex:\centerline{\resizebox{!}{4in}{\includegraphics{H64-flaw.eps}}}
pset10/fall99sol.tex:\usepackage{graphics}
pset10/fall99sol.tex:\centerline{\resizebox{!}{3in}{\includegraphics{H64-tennis.eps}}}
pset10/fall99sol.tex:\centerline{\resizebox{!}{4in}{\includegraphics{H64-flaw.eps}}}
pset10/spring97.tex:\problem How many ways can a photographer at a wedding arrange 6
pset10/spring97.tex:How many graphs are there on 4 distinguishable vertices that do not
pset10/spring97sol.tex:\problem How many ways can a photographer at a wedding arrange 6
pset10/spring97sol.tex:How many graphs are there on 4 distinguishable vertices that do not
pset10/spring97sol.tex:There are ${4 \choose 2} = 6$ possible edges, so there are $2^6 = 64$ graphs
pset10/spring97sol.tex:of $4$ vertices. Now we use inclusion-exclusion to compute the number of graphs
pset10/spring97sol.tex:Let $A_i$ denote the set of graphs that have a cycle facing vertex $i$.  
pset10/spring97sol.tex:For example, $A_1$ is the set of graphs containing the cycle $2,3,4,2$.
pset10/spring97sol.tex:number of graphs having two or more cycles of length $3$.  There are 
pset10/spring97sol.tex:the resulting graphs (by either including or excluding the remaining edge).
pset10/spring97sol.tex:consisting of intersection of three graphs containing cycles.  There are
pset10/spring97sol.tex:${4 \choose 3} = 4$ ways to choose the vertices, and just one graph of this 
pset10/spring97sol.tex:type ($K_4$). Finally we consider the intersection of the graphs containing 
pset10/spring97sol.tex:In total there are $32 - 12 + 4 - 1 = 23$ graphs containing cycles of length
pset10/spring97sol.tex:$3$, so there are $64 - 23 = 41$ graphs without length $3$ cycles.
pset10/spring99.tex:%\usepackage{graphics}
pset10/spring99sol.tex:\usepackage{graphics}
pset11/fall98sol.tex:\usepackage{graphics}
pset11/fall99.tex:\usepackage{amsmath} %,graphicx}
pset11/fall99sol.tex:\usepackage{amsmath} %,graphicx}
pset11/spring99.tex:\usepackage{graphics}
pset11/spring99sol.tex:\usepackage{graphics}
pset12/fall99.tex:\usepackage{amsmath,graphicx}
pset12/fall99sol.tex:\usepackage{amsmath,graphicx}
pset12/spring97.tex:graph with the following bizarre property: for every set of $k$ people
pset12/spring97sol.tex:graph with the following bizarre property: for every set of $k$ people
pset2/fall98sol.tex:\usepackage{graphics}
pset2/fall98sol.tex:\centerline{\resizebox{!}{2.0in}{\includegraphics{ps2.eps}}}
pset2/fall99.tex:%\usepackage{graphics}
pset2/fall99sol.tex:%\usepackage{graphics}
pset2/spring94.tex:\oproblem Let $G=(V,E)$ be an undirected graph, and let $r:V\to\reals$
pset2/spring94.tex:average of the values of $v$'s neighbors.  Prove that if the graph is
pset2/spring94.tex:\oproblem Let $G=(V,E)$ be an $n$-vertex dag (directed acyclic graph).
pset2/spring94.tex:\oproblem Prove that edges of any connected, undirected graph with an
pset2/spring94.tex:\oproblem Prove that any graph on $6$ vertices contains $3$ vertices
pset2/spring94.tex:%% 	that for any (k,l), there is some n s.t. any graph on n nodes has
pset2/spring94.tex:\oproblem Prove that each vertex of an undirected graph can be colored
pset2/spring94.tex:\wproblem Each vertex of an undirected graph $G=(V,E)$ contains a
pset2/spring94.tex:graph $G$, there exists a \defi{good} setting of the switches: a
pset2/spring94.tex:vertices.  Prove that if every graph on $\card{V}-1$ vertices has a
pset2/spring94.tex:corresponding to the subgraphs induced (see Handout 9, page 88) by the
pset2/spring94.tex:includes $v$ and its neighbors.  Prove that if every graph on
pset2/spring94.tex:subgraphs induced by some $\card{V}-\card{S}$ subsets of $V$ that have
pset2/spring94.tex:graph.
pset2/spring94.tex:\wproblem A \defi{hamiltonian path} in an undirected graph is a simple
pset2/spring94.tex:path that visits all the vertices.  An undirected graph is said to be
pset2/spring94.tex:graph~$G$, where we assume $A[v,v]=1$ for all $v\in V$.  The
pset2/spring94.tex:\defi{cube} of $G$ is the graph $G^3=(V,E^3)$ whose adjacency matrix
pset2/spring94.tex:graph is hamiltonian.
pset2/spring94.tex:\problempart Prove that any connected graph contains a free tree that
pset2/spring94.tex:connects all the vertices as a subgraph.
pset2/spring94.tex:conclude that the cube of any connected graph is Hamiltonian.
pset3/fall94.tex:Construct an undirected graph containing a node for each square of the
pset3/fall94.tex:\problem Prove that in any undirected graph, the sum of the squares of
pset3/fall94.tex:tree is considered to be a free tree (that is, a graph) or a rooted
pset3/fall94.tex:a rooted tree is one fewer than its graph degree.  (See the footnote
pset3/fall94.tex:\problem Prove that the vertices of an undirected graph can be colored
pset3/fall94.tex:  \problem Prove that the edges of any connected, undirected graph with 
pset3/fall94.tex:vertex of an undirected graph $G=(V,E)$ contains a toggle switch and a
pset3/fall94.tex:problem focuses on showing that no matter what graph underlies the
pset3/fall94.tex:of this problem is to prove that for any undirected graph $G$, there
pset3/fall94.tex:The proof is by induction on the number of vertices in the graph.
pset3/fall94.tex:switches for any graph $G$ on $n$ vertices by assuming that there is
pset3/fall94.tex:such a setting for any graph on $n-1$ vertices.  We shall need to
pset3/fall94.tex:Assume that every graph on $n-1$ vertices has a good setting.  Notice
pset3/fall94.tex:subgraphs\footnote{The \defi{induced subgraph} on $S \subset V$ is the
pset3/fall94.tex:graph obtained by removing all nodes (and incident edges) not in~$S$.
pset3/fall94.tex:Assume that every graph on $n-1$ vertices has a good setting.  Let $v$
pset3/fall94.tex:Conclude that a good setting exists for any undirected graph.
pset3/fall97.tex:Let $G$ be a bipartite graph with $n$ vertices and $m$ edges.
pset3/fall97.tex:graphs $K_n,C_n$ and $W_n$ defined in 7.3 of Rosen.
pset3/fall97.tex:Let $G=(V,E)$ be an undirected graph, and let there be a weight $r(v)$
pset3/fall97.tex:average of the values of $v$'s neighbors.  Prove that if the graph is
pset3/fall97.tex:Prove that in any undirected graph, the sum of the squares of
pset3/fall97.tex:Let $G$ be a graph with $n$ vertices and $m$ edges. Let $dmax$ be the
pset3/fall97.tex:F1)  Any subgraph of a planar graph is planar.
pset3/fall97.tex:F2) Any planar graph with $n$ vertices and $m$ edges satisfies
pset3/fall97.tex:(F3) Any planar graph has a node of degree at most $5$.\\
pset3/fall97.tex:\ppart Use F1 and F3 to show that any planar graph can be colored with six colors.
pset3/fall97.tex:Show that a directed multigraph  has an Euler
pset3/fall97.tex:circuit if and only if the graph is weakly connected (see Rosen 
pset3/fall97.tex:{\em Definition:} A {\em tree} is a connected graph such that
pset3/fall97.tex:to be an acyclic graph of $n$ vertices that has $n-1$ edges.
pset3/fall97.tex:%equivalence relations and graphs
pset3/fall97.tex:\ppart Let $G$ be simple a graph.  Define a relation $R$ on the set of vertices $V$
pset3/fall97sol.tex:Let $G$ be a bipartite graph with $n$ vertices and $m$ edges.
pset3/fall97sol.tex:edges the graph may have is $k(n-k)$.  The maximum of the function 
pset3/fall97sol.tex:graphs $K_n,C_n$ and $W_n$ defined in 7.3 of Rosen.
pset3/fall97sol.tex:Let $G=(V,E)$ be an undirected graph, and let there be a weight $r(v)$
pset3/fall97sol.tex:average of the values of $v$'s neighbors.  Prove that if the graph is
pset3/fall97sol.tex:Suppose that not all the vertices in the graph have the same value.
pset3/fall97sol.tex:the graph. Choose a vertex $v$ such that $r(v) = s$ and $v$ has a neighbor
pset3/fall97sol.tex:Prove that in any undirected graph, the sum of the squares of
pset3/fall97sol.tex:vertices of the graph.
pset3/fall97sol.tex:Let $E$ be the set of edges of the graph and
pset3/fall97sol.tex:$V = \{ v_1, \ldots , v_n \}$ be the set of vertices of the graph.
pset3/fall97sol.tex:A connected subgraph of a tree is itself a tree.
pset3/fall97sol.tex:A tree $T$ is a connected graph with unique paths between any two vertices.
pset3/fall97sol.tex:Let $H$ be a connected subgraph of $T$.  Since $H$ is connected there is
pset3/fall97sol.tex:one connecting them with $v$. Let $H_1, \ldots , H_{k+1}$ be the subgraphs 
pset3/fall97sol.tex:Let $G$ be a graph with $n$ vertices and $m$ edges. Let $dmax$ be the
pset3/fall97sol.tex:F1)  Any subgraph of a planar graph is planar.
pset3/fall97sol.tex:F2) Any planar graph with $n$ vertices and $m$ edges satisfies
pset3/fall97sol.tex:(F3) Any planar graph has a vertex of degree at most $5$.\\
pset3/fall97sol.tex:\ppart Use F1 and F3 to show that any planar graph can be colored with six colors.
pset3/fall97sol.tex:$P(n) = $ ``A planar graph of $n$ vertices can be colored with at most
pset3/fall97sol.tex:Let $G$ be a planar graph with $n+1$ vertices and remove a vertex $v$ 
pset3/fall97sol.tex:$5$ (or less).  The remaining $n$-vertex graph can be colored with $6$ colors
pset3/fall97sol.tex:Show that a directed multigraph has an Euler
pset3/fall97sol.tex:circuit if and only if the graph is weakly connected and the in-degree and
pset3/fall97sol.tex:First we will show that if the multigraph has an Euler circuit, then the 
pset3/fall97sol.tex:graph is weakly connected and the  in-degree and
pset3/fall97sol.tex:Suppose that the directed multigraph has an Euler circuit.  Since the circuit
pset3/fall97sol.tex:provides a path from any vertex to any other vertex, the graph is strongly
pset3/fall97sol.tex:Conversely, suppose that we have a directed multigraph $G$ which is weakly 
pset3/fall97sol.tex:repeated edges) in the graph.  If $C$ contains all the edges in $G$
pset3/fall97sol.tex:Now consider the subgraph $G-C$. Note that $v$ is a vertex of  $G-C$. 
pset3/fall97sol.tex:Now consider the cycle in the original graph $G$ that starts at
pset3/fall97sol.tex:{\em Definition:} A {\em tree} is a connected graph such that
pset3/fall97sol.tex:to be an acyclic graph of $n$ vertices that has $n-1$ edges.
pset3/fall97sol.tex:Let $G$ be a graph  of $n$ vertices such that
pset3/fall97sol.tex:$G$ is connected.  So $G$ is a connected acyclic graph, and from class
pset3/fall97sol.tex:Conversely, let $G$ be an acyclic graph with $n$ vertices and $n-1$ edges.
pset3/fall97sol.tex:We know from class that such a graph is connected so there exists at least 
pset3/fall97sol.tex:from $C'$ (such a vertex exists because the graphs are distinct).  
pset3/fall97sol.tex:This contradicts the acyclicity of the graph.
pset3/fall97sol.tex:%equivalence relations and graphs
pset3/fall97sol.tex:\ppart Let $G$ be a simple graph.  Define a relation $R$ on the set of vertices $V$
pset3/fall98.tex:\usepackage{graphics}
pset3/fall98.tex:\centerline{\resizebox{!}{1.0in}{\includegraphics{ps3-relation-cx.eps}}}
pset3/fall98.tex:Let $G_n$ be a directed graph with vertices numbered $0, 1,
pset3/fall98.tex:\problempart Draw the directed graphs $G_1$, $G_2$, and $G_3$.
pset3/fall98.tex:\centerline{\resizebox{4.0in}{!}{\includegraphics{ps3-digraph.eps}}}
pset3/fall98.tex:acyclic graph.
pset3/fall98.tex:Consider the following sequence of vertices in graph $G_n$.
pset3/fall98.tex:be distinct, since the graph contains only $n$ vertices.  Suppose
pset3/fall98.tex:Therefore, $G_n$ is not a directed acyclic graph.
pset3/fall98.tex:\centerline{\resizebox{!}{1.5in}{\includegraphics{ps3-partial.eps}}}
pset3/fall98.tex:\centerline{\resizebox{!}{1.5in}{\includegraphics{ps3-partial2.eps}}}
pset3/fall98.tex:\centerline{\resizebox{!}{1.5in}{\includegraphics{ps3-poset-cx.eps}}}
pset3/fall98.tex:An {\em automorphism} of a graph is a relabeling of the
pset3/fall98.tex:vertices that preserves adjacency.  For example, the graph on the left
pset3/fall98.tex:relabeled $y$.)  The relabeled graph is shown on the right side of the
pset3/fall98.tex:preserved; that is, in the relabeled graph, just as in the original,
pset3/fall98.tex:graph has a {\em trivial automorphism} that assigns each node its
pset3/fall98.tex:\centerline{\resizebox{!}{1.5in}{\includegraphics{ps3-auto.eps}}}
pset3/fall98.tex:\problempart List all non-trivial automorphisms of the graph below using the
pset3/fall98.tex:\centerline{\resizebox{!}{2.0in}{\includegraphics{ps3-findauto.eps}}}
pset3/fall98.tex:\problempart Draw a graph with at least 2 nodes that has only the trivial
pset3/fall98.tex:\centerline{\resizebox{!}{1.0in}{\includegraphics{ps3-noauto.eps}}}
pset3/fall98.tex:An $n$-node graph is said to be {\em tangled} if there is an edge
pset3/fall98.tex:a special case, the graph consisting of a single node is considered
pset3/fall98.tex:{\bf Claim.} Every non-empty, tangled graph is connected.
pset3/fall98.tex:graph.  Let $P(n)$ be the propostion that if an $n$-node graph is
pset3/fall98.tex:because the graph consisting of a single node is defined to be tangled
pset3/fall98.tex:graph is tangled, then it is connected.  Let $G$ be a tangled,
pset3/fall98.tex:$(n+1)$-node graph.  Arbitrarily partition $G$ into two pieces so that
pset3/fall98.tex:$n \geq 1$, the graph $G$ has a least two vertices, and so both pieces
pset3/fall98.tex:is connected.  Since the graph $G$ is tangled, there is an edge
pset3/fall98.tex:the entire graph is connected.  This shows that $P(1), \ldots, P(n)$
pset3/fall98.tex:says; the induction hypothesis states that {\em if a graph is
pset3/fall98.tex:\problempart Draw a tangled graph that is not connected.
pset3/fall98.tex:\centerline{\resizebox{!}{1in}{\includegraphics{ps3-tangled-cx.eps}}}
pset3/fall98.tex:\problempart An $n$-node graph is said to be {\em mangled} if there is an edge
pset3/fall98.tex:Again, as a special case, the graph consisting of a single node is
pset3/fall98.tex:{\bf Claim.} Every non-empty, mangled graph is connected.
pset3/fall98.tex:contradiction that these exists an $n$-node graph that is mangled, but
pset3/fall98.tex:not connected.  Then the graph must have at least two connected
pset3/fall98.tex:with more than $\lceil\frac{n}{2}\rceil$ vertices, since the graph has
pset3/fall98.tex:graph is mangled, there is an edge leaving this component.  But this
pset3/fall98.tex:Let $G$ and $H$ be undirected graphs with no self-loops.  The {\em
pset3/fall98.tex:product graph} $P = G \times H$ is defined as follows.  The vertex set
pset3/fall98.tex:edges in the product graph $P$ are of two types.  First, for every
pset3/fall98.tex:\problempart Draw the product of the two graphs shown below.  
pset3/fall98.tex:\centerline{\resizebox{!}{1in}{\includegraphics{ps3-twographs.eps}}}
pset3/fall98.tex:\centerline{\resizebox{!}{1.5in}{\includegraphics{ps3-product.eps}}}
pset3/fall98.tex:\problempart Let $G$ be the graph consisting of two vertices connected
pset3/fall98.tex:graph.  Therefore, there are $2^n \cdot 2 = 2^{n+1}$ vertices in
pset3/fall98sol.tex:\usepackage{graphics}
pset3/fall98sol.tex:\centerline{\resizebox{!}{1.0in}{\includegraphics{ps3-relation-cx.eps}}}
pset3/fall98sol.tex:Let $G_n$ be a directed graph with vertices numbered $0, 1,
pset3/fall98sol.tex:\problempart Draw the directed graphs $G_1$, $G_2$, and $G_3$.
pset3/fall98sol.tex:\centerline{\resizebox{4.0in}{!}{\includegraphics{ps3-digraph.eps}}}
pset3/fall98sol.tex:acyclic graph.
pset3/fall98sol.tex:Consider the following sequence of vertices in graph $G_n$.
pset3/fall98sol.tex:be distinct, since the graph contains only $n$ vertices.  Suppose
pset3/fall98sol.tex:Therefore, $G_n$ is not a directed acyclic graph.
pset3/fall98sol.tex:\centerline{\resizebox{!}{1.5in}{\includegraphics{ps3-partial.eps}}}
pset3/fall98sol.tex:\centerline{\resizebox{!}{1.5in}{\includegraphics{ps3-partial2.eps}}}
pset3/fall98sol.tex:\centerline{\resizebox{!}{1.5in}{\includegraphics{ps3-poset-cx.eps}}}
pset3/fall98sol.tex:An {\em automorphism} of a graph is a relabeling of the
pset3/fall98sol.tex:vertices that preserves adjacency.  For example, the graph on the left
pset3/fall98sol.tex:relabeled $y$.)  The relabeled graph is shown on the right side of the
pset3/fall98sol.tex:preserved; that is, in the relabeled graph, just as in the original,
pset3/fall98sol.tex:graph has a {\em trivial automorphism} that assigns each node its
pset3/fall98sol.tex:\centerline{\resizebox{!}{1.5in}{\includegraphics{ps3-auto.eps}}}
pset3/fall98sol.tex:\problempart List all non-trivial automorphisms of the graph below using the
pset3/fall98sol.tex:\centerline{\resizebox{!}{1.5in}{\includegraphics{ps3-findauto.eps}}}
pset3/fall98sol.tex:\problempart Draw a graph with at least 2 nodes that has only the trivial
pset3/fall98sol.tex:\centerline{\resizebox{!}{1.0in}{\includegraphics{ps3-noauto.eps}}}
pset3/fall98sol.tex:An $n$-node graph is said to be {\em tangled} if there is an edge
pset3/fall98sol.tex:a special case, the graph consisting of a single node is considered
pset3/fall98sol.tex:{\bf Claim.} Every non-empty, tangled graph is connected.
pset3/fall98sol.tex:graph.  Let $P(n)$ be the propostion that if an $n$-node graph is
pset3/fall98sol.tex:because the graph consisting of a single node is defined to be tangled
pset3/fall98sol.tex:graph is tangled, then it is connected.  Let $G$ be a tangled,
pset3/fall98sol.tex:$(n+1)$-node graph.  Arbitrarily partition $G$ into two pieces so that
pset3/fall98sol.tex:$n \geq 1$, the graph $G$ has a least two vertices, and so both pieces
pset3/fall98sol.tex:is connected.  Since the graph $G$ is tangled, there is an edge
pset3/fall98sol.tex:the entire graph is connected.  This shows that $P(1), \ldots, P(n)$
pset3/fall98sol.tex:says; the induction hypothesis states that {\em if a graph is
pset3/fall98sol.tex:\problempart Draw a tangled graph that is not connected.
pset3/fall98sol.tex:\centerline{\resizebox{!}{1in}{\includegraphics{ps3-tangled-cx.eps}}}
pset3/fall98sol.tex:\problempart An $n$-node graph is said to be {\em mangled} if there is an edge
pset3/fall98sol.tex:Again, as a special case, the graph consisting of a single node is
pset3/fall98sol.tex:{\bf Claim.} Every non-empty, mangled graph is connected.
pset3/fall98sol.tex:contradiction that these exists an $n$-node graph that is mangled, but
pset3/fall98sol.tex:not connected.  Then the graph must have at least two connected
pset3/fall98sol.tex:with more than $\lceil\frac{n}{2}\rceil$ vertices, since the graph has
pset3/fall98sol.tex:graph is mangled, there is an edge leaving this component.  But this
pset3/fall98sol.tex:Let $G$ and $H$ be undirected graphs with no self-loops.  The {\em
pset3/fall98sol.tex:product graph} $P = G \times H$ is defined as follows.  The vertex set
pset3/fall98sol.tex:edges in the product graph $P$ are of two types.  First, for every
pset3/fall98sol.tex:\problempart Draw the product of the two graphs shown below.  
pset3/fall98sol.tex:\centerline{\resizebox{!}{1in}{\includegraphics{ps3-twographs.eps}}}
pset3/fall98sol.tex:\centerline{\resizebox{!}{1.5in}{\includegraphics{ps3-product.eps}}}
pset3/fall98sol.tex:\problempart Let $G$ be the graph consisting of two vertices connected
pset3/fall98sol.tex:graph.  Therefore, there are $2^n \cdot 2 = 2^{n+1}$ vertices in
pset3/spring94.tex:%	Recall that any connected graph $G$ contains a free tree as a subgraph.
pset3/spring94.tex:Argue by looking at a directed graph on $n$
pset3/spring94sol.tex:Consider the directed graph with  an edge from node $u$ to node $v$
pset3/spring94sol.tex:If there are fewer than $n-1$ edges then the graph is not connected.
pset3/spring94sol.tex:The nodes of the graph can therefore be partitioned into two disjoint
pset3/spring98.tex:The graphs  $C_n$, $Q_n$, $W_n$, and $K_{n,m}$ are defined in Rosen 7.2.
pset3/spring98.tex:graph $Q_{n+1}$.  \hint Use the matrix of $Q_n$ and suitable identity
pset3/spring98.tex:\ppart Prove or disprove that the pair of graphs given in Rosen 7.3,
pset3/spring98.tex:\ppart Prove or disprove that the pair of graphs given in Rosen 7.3,
pset3/spring98.tex:Some properties of a simple graph, $G$, are described below.  For each
pset3/spring98.tex:A simple graph, $G$, has {\em inherited degree $d \geq 0$ }
pset3/spring98.tex:(ii) there is a vertex $v \in G$ of degree $\leq d$, and the subgraph of
pset3/spring98.tex:Prove that if a graph has inherited degree $d$, then it is
pset3/spring98.tex:For every $n>0$, describe an example of a graph which does not have
pset3/spring98sol.tex:The graphs  $C_n$, $Q_n$, $W_n$, and $K_{n,m}$ are defined in Rosen 7.2.
pset3/spring98sol.tex:vertices and a group of $m$ vertices. In this graph, an edge is
pset3/spring98sol.tex:graph $Q_{n+1}$.  \hint Use the matrix of $Q_n$ and suitable identity
pset3/spring98sol.tex:are $Q_n$, which correspond to the two subgraphs $Q_n$ in $Q_{n+1}$. The right top and left bottom quarter of the matrix
pset3/spring98sol.tex:connects two vertices in the same group in a bipartite graph, no two adjacent vertices have the same color. 
pset3/spring98sol.tex:any complete bipartite graph is 2-colorable.
pset3/spring98sol.tex:\ppart Prove or disprove that the pair of graphs given in Rosen 7.3,
pset3/spring98sol.tex:The two graphs are isomorphic. Informally, we can see by breaking the graph
pset3/spring98sol.tex:between the two graphs. We can verify this since there is an edge between
pset3/spring98sol.tex:\ppart Prove or disprove that the pair of graphs given in Rosen 7.3,
pset3/spring98sol.tex:The two graphs are not isomorphic. Both graphs have two vertices of 
pset3/spring98sol.tex:degree 3: $u_2$ and $u_3$ in the first graph and $v_2$ and $v_4$ 
pset3/spring98sol.tex:in the second graph.  
pset3/spring98sol.tex:the two graphs are not isomorphic.
pset3/spring98sol.tex:Some properties of a simple graph, $G$, are described below.  For each
pset3/spring98sol.tex:mapping between the vertices of two isomorphic graphs. Therefore, the number 
pset3/spring98sol.tex:of vertices in the two graphs must be
pset3/spring98sol.tex:the same. If one graph has even number of vertices, then the other must
pset3/spring98sol.tex:exists a one-to-one and onto function $f$ mapping from vertices of one graph 
pset3/spring98sol.tex:first graph if and only if $f(a)$ and $f(b)$ are adjacent in the  second
pset3/spring98sol.tex:graph, for all $a$ and $b$ in the first graph. \\
pset3/spring98sol.tex:So, for example, let $G_1$ be a graph with a single vertex, 1, and $G_2$ be
pset3/spring98sol.tex:a graph with a single vertex, 2. Obviously the two graphs are isomorphic, but
pset3/spring98sol.tex:Let $G_1, G_2$ be simple graphs and $f:V_1\to V_2$ be an isomorphism
pset3/spring98sol.tex:Prove by contradiction:  Let a graph $G_1$ has exactly one vertex of 
pset3/spring98sol.tex:degree $3$ while another graph $G_2$ does not have exactly one vertex of 
pset3/spring98sol.tex:degree 3. Suppose the two graphs are isomorphic. If $G_2$ does not have 
pset3/spring98sol.tex:Let $G_1$ be a graph with three vertices, $1$, $2$ and $\{1,2\}$. There is
pset3/spring98sol.tex:On the other hand, let $G_2$ be a graph with three vertices,
pset3/spring98sol.tex:Obviously two graphs are isomorphic; however, $G_2$ does not have 
pset3/spring98sol.tex:A simple graph, $G$, has {\em inherited degree $d \geq 0$ }
pset3/spring98sol.tex:(ii) there is a vertex $v \in G$ of degree $\leq d$, and the subgraph of
pset3/spring98sol.tex:The graph $G$ obtained by removing a vertex of degree $3$ has $n-2$ vertices
pset3/spring98sol.tex:%Since this single vertex graph has
pset3/spring98sol.tex:%{\em inherited degree 3}, the graph right before (two verticies)
pset3/spring98sol.tex:%degree $\leq d$ until every vertex in the subgraph has 
pset3/spring98sol.tex:%degree $\leq d$ then the original graph before the vertices are removed
pset3/spring98sol.tex:Rosen, 8.1: a tree is a connected undirected graph with no simple
pset3/spring98sol.tex:Then we need to show that the subgraph
pset3/spring98sol.tex:In a finite graph, a path of length greater than or equal to 
pset3/spring98sol.tex:number of vertices.  Therefore in any finite graph there must be longest
pset3/spring98sol.tex:contradicts that the graph is a tree.
pset3/spring98sol.tex:Second, let's prove that the subgraph constructed by removing one leaf
pset3/spring98sol.tex:book (cf. Rosen p531), a tree is a connected undirected graph with no simple
pset3/spring98sol.tex:get disconnected. In other words, the subgraph is still connected.
pset3/spring98sol.tex:%that leaf can only be connected to the graph via the adjacent vertex, 
pset3/spring98sol.tex:%the subgraph is still connected. 
pset3/spring98sol.tex:Since the subgraph is a connected undirected 
pset3/spring98sol.tex:graph with no simple circuits, it is also a tree.\\
pset3/spring98sol.tex:Since every tree has a leaf(vertex with degree 1) and the subgraph
pset3/spring98sol.tex:Prove that if a graph has inherited degree $d$, then it is
pset3/spring98sol.tex:vertices in a graph to prove this fact. 
pset3/spring98sol.tex:Let $P(n)$::= ``$\forall d>0$, any $n$-vertex graphs with inherited degree $d$ is $(d+1)$ colorable.''  
pset3/spring98sol.tex:{\bf Base Case}: $n=1$. There is only one 1-vertex graph. And it is obviously
pset3/spring98sol.tex:prove $P(n+1)$ is true. Given any $(n+1)$-vertex graph $G$ with inherited degree $d$ for any $d>0$, 
pset3/spring98sol.tex:\item There is a vertex $v\in G$ of degree $\leq d$, and the subgraph
pset3/spring98sol.tex:Therefore, by induction, every graph with inherited degree $d$ is $(d+1)$-colorable.\\
pset3/spring98sol.tex:%following method to color a graph with inherited degree $d$.
pset3/spring98sol.tex:%Then, we can easily show that every graph with all the vertices with
pset3/spring98sol.tex:%The base case is a graph with one vertex. It is true since only one
pset3/spring98sol.tex:%let's consider a graph $G_{n+1}$ with $n+1$ vertices of degree $\leq d$.
pset3/spring98sol.tex:%Let's remove a vertex from $G$ and let say the remaining graph is $G_n$.
pset3/spring98sol.tex:%vertex we took out back to the graph. Since that vertex can be adjacent
pset3/spring98sol.tex:%Therefore, we proved that every graph with all the vertices with degree
pset3/spring98sol.tex:%the original graph with inherited degree $d$, since we can always 
pset3/spring98sol.tex:%Any graph with inherited degree $d$ is (d+1) colorable.\\
pset3/spring98sol.tex:For every $n>0$, describe an example of a graph which does not have
pset3/spring98sol.tex:However, it is $2$-colorable since every complete bipartite graph is $2$-colorable.
pset3/spring99.tex:\usepackage{graphics}
pset3/spring99.tex:Assume that all graphs are simple--- undirected with no multi-edges or
pset3/spring99.tex:\problem {\bf (10 points)} The adjacency matrix of a graph is given below.
pset3/spring99.tex:\problempart Draw the graph defined by this adjacency matrix.  Label
pset3/spring99.tex:the vertices of your graph $1, 2, \ldots, 6$ so that vertex $i$
pset3/spring99.tex:\centerline{\resizebox{!}{2.0in}{\includegraphics{adjgraph.eps}}}
pset3/spring99.tex:\problempart Determine the chromatic number of this graph, and
pset3/spring99.tex:chromatic number of the graph is exactly 3.}
pset3/spring99.tex:\problem {\bf (10 points)} Let $G$ be a graph.  Prove that there is a
pset3/spring99.tex:If graph $G$ has no vertex of odd degree, then the claim is true
pset3/spring99.tex:\problem {\bf (15 points)} An edge of a connected graph is called a {\em
pset3/spring99.tex:cut-edge} if removing the edge disconnects the graph.  Prove that an
pset3/spring99.tex:edge $e$ in a connected graph $G$ is a cut-edge if and only if no
pset3/spring99.tex:$P$ traverses the edge $e$.)  This shows that the graph remains
pset3/spring99.tex:between every pair of distinct vertices in a connected graph.  Since
pset3/spring99.tex:$e$ is not a cut-edge, the graph obtained by removing edge $e$ is
pset3/spring99.tex:removed from the graph.  Adjoining edge $e$ to path $P$ gives a simple
pset3/spring99.tex:\problem {\bf (15 points)} A graph $G$ is {\em self-complementary} if
pset3/spring99.tex:a graph, is defined in problem 33 on page 456 of Rosen (p.449 in
pset3/spring99.tex:\problempart Draw a self-complementary graph with more than one
pset3/spring99.tex:\solution{The simplest solution is given below.  Edges of the graph
pset3/spring99.tex:\centerline{\resizebox{!}{1.5in}{\includegraphics{selfcomp.eps}}}
pset3/spring99.tex:graph with $n$ vertices.  No proof is required.
pset3/spring99.tex:\solution{In a complete graph, each of the $n$ vertices is joined by
pset3/spring99.tex:complete graph with $n$ vertices is
pset3/spring99.tex:\problempart Show that if a graph $G$ is self-complementary, then the
pset3/spring99.tex:number of edges in the complementary graph $\bar{G}$, and let $n$ be
pset3/spring99.tex:the number of vertices in each of these graphs.  If $G$ is
pset3/spring99.tex:every edge in the complete graph on $n$ vertices is contained in
pset3/spring99.tex:exactly one of the graphs $G$ and $\bar{G}$.  Therefore, $m + \bar{m}
pset3/spring99.tex:Since the number of edges in a graph must be an integer, $n (n-1)$
pset3/spring99.tex:must be a multiple of 4.  That is, a self-complementary graph must
pset3/spring99.tex:graph.
pset3/spring99.tex:\solution{We can represent this table using a weighted, directed graph
pset3/spring99.tex:%\centerline{\resizebox{!}{2.5in}{\includegraphics{exchange.eps}}}
pset3/spring99.tex:exchanges.  Identify the abstract property that your graph must
pset3/spring99.tex:your graph has this property.
pset3/spring99.tex:The graph does contain at least one such cycle, which is shown with a
pset3/spring99.tex:in $n$-cubes.  A {\em Hamiltonian circuit} in a graph is a circuit
pset3/spring99.tex:traversing every vertex in the graph exactly once.  The $n$-cube is
pset3/spring99.tex:\centerline{\resizebox{!}{2.0in}{\includegraphics{fourcube.eps}}}
pset3/spring99.tex:\problem {\bf (10 points)} The weighted graph below represents a system
pset3/spring99.tex:\centerline{\resizebox{!}{2.0in}{\includegraphics{flowprob.eps}}}
pset3/spring99.tex:\centerline{\resizebox{!}{2.0in}{\includegraphics{flowsol.eps}}}
pset3/spring99.tex:of graph.
pset3/spring99.tex:form of a directed acyclic graph.  Each vertex represents a task,
pset3/spring99.tex:\centerline{\resizebox{!}{3.0in}{\includegraphics{conquest.eps}}}
pset3/spring99sol.tex:\usepackage{graphics}
pset3/spring99sol.tex:Assume that all graphs are simple--- undirected with no multi-edges or
pset3/spring99sol.tex:\problem {\bf (10 points)} The adjacency matrix of a graph is given below.
pset3/spring99sol.tex:\problempart Draw the graph defined by this adjacency matrix.  Label
pset3/spring99sol.tex:the vertices of your graph $1, 2, \ldots, 6$ so that vertex $i$
pset3/spring99sol.tex:\centerline{\resizebox{!}{2.0in}{\includegraphics{adjgraph.eps}}}
pset3/spring99sol.tex:\problempart Determine the chromatic number of this graph, and
pset3/spring99sol.tex:chromatic number of the graph is exactly 3.}
pset3/spring99sol.tex:\problem {\bf (10 points)} Let $G$ be a graph.  Prove that there is a
pset3/spring99sol.tex:If graph $G$ has no vertex of odd degree, then the claim is true
pset3/spring99sol.tex:If graph $G$ has no vertex of odd degree, then the claim is true
pset3/spring99sol.tex:be the subgraph of graph $G$ consisting of the connected component
pset3/spring99sol.tex:\problem {\bf (15 points)} An edge of a connected graph is called a {\em
pset3/spring99sol.tex:cut-edge} if removing the edge disconnects the graph.  Prove that an
pset3/spring99sol.tex:edge $e$ in a connected graph $G$ is a cut-edge if and only if no
pset3/spring99sol.tex:$P$ traverses the edge $e$.)  This shows that the graph remains
pset3/spring99sol.tex:between every pair of distinct vertices in a connected graph.  Since
pset3/spring99sol.tex:$e$ is not a cut-edge, the graph obtained by removing edge $e$ is
pset3/spring99sol.tex:removed from the graph.  Adjoining edge $e$ to path $P$ gives a simple
pset3/spring99sol.tex:\problem {\bf (15 points)} A graph $G$ is {\em self-complementary} if
pset3/spring99sol.tex:a graph, is defined in problem 33 on page 456 of Rosen (p. 449 in
pset3/spring99sol.tex:\problempart Draw a self-complementary graph with more than one
pset3/spring99sol.tex:\solution{The simplest solution is given below.  Edges of the graph
pset3/spring99sol.tex:\centerline{\resizebox{!}{1.5in}{\includegraphics{selfcomp.eps}}}
pset3/spring99sol.tex:graph with $n$ vertices.  No proof is required.
pset3/spring99sol.tex:\solution{In a complete graph, each of the $n$ vertices is joined by
pset3/spring99sol.tex:complete graph with $n$ vertices is
pset3/spring99sol.tex:\problempart Show that if a graph $G$ is self-complementary, then the
pset3/spring99sol.tex:number of edges in the complementary graph $\bar{G}$, and let $n$ be
pset3/spring99sol.tex:the number of vertices in each of these graphs.  If $G$ is
pset3/spring99sol.tex:every edge in the complete graph on $n$ vertices is contained in
pset3/spring99sol.tex:exactly one of the graphs $G$ and $\bar{G}$.  Therefore, $m + \bar{m}
pset3/spring99sol.tex:Since the number of edges in a graph must be an integer, $n (n-1)$
pset3/spring99sol.tex:must be a multiple of 4.  That is, a self-complementary graph must
pset3/spring99sol.tex:graph.
pset3/spring99sol.tex:\solution{We can represent this table using a weighted, directed graph
pset3/spring99sol.tex:\centerline{\resizebox{!}{3.0in}{\includegraphics{exchange.eps}}}
pset3/spring99sol.tex:exchanges.  Identify the abstract property that your graph must
pset3/spring99sol.tex:your graph has this property.
pset3/spring99sol.tex:The graph does contain at least one such cycle, which is shown with a
pset3/spring99sol.tex:in $n$-cubes.  A {\em Hamiltonian circuit} in a graph is a circuit
pset3/spring99sol.tex:traversing every vertex in the graph exactly once.  The $n$-cube is
pset3/spring99sol.tex:\centerline{\resizebox{!}{2.0in}{\includegraphics{fourcube.eps}}}
pset3/spring99sol.tex:of graph.
pset3/spring99sol.tex:form of a directed acyclic graph.  Each vertex represents a task,
pset3/spring99sol.tex:\centerline{\resizebox{!}{3.0in}{\includegraphics{conquest.eps}}}
pset4/fall94.tex:The directed graph 
pset4/fall94.tex:\problem	%% friendly graphs from [CLR], Problem 5-2 on p. 97.
pset4/fall94.tex:graphs.  Assume that friendship is symmetric but
pset4/fall94.tex:  Show that any graph with degree at least $n/2$ (that is, each of the $n$ 
pset4/fall94.tex:  A {\defi clique} is a graph with edges between all pairs of vertices.
pset4/fall94.tex:  An {\defi independent set} is a graph with no edges.
pset4/fall94.tex:  such that every graph on $n$ nodes has (as an induced subgraph) 
pset4/fall94.tex:  %% 	that for any (k,l), there is some n s.t. any graph on n nodes has
pset4/fall94.tex:  Let $G=(V,E)$ be an $n$-vertex dag (directed acyclic graph).  First
pset4/fall94.tex:Prove that the edges of any connected, undirected graph with 
pset4/fall94.tex:the orientation of each edge along an undirected path in the graph?)
pset4/fall94.tex:  A graph that contains no cycles but has fewer than $n-1$ edges (on $n$ nodes)
pset4/fall94.tex:  that is, the graph can be partitioned into $n-m$ sets such that 
pset4/fall94.tex:  \problem Let $G=(V,E)$ be an undirected graph, and let $r:V\to\reals$
pset4/fall94.tex:  average of the values of $v$'s neighbors.  Prove that if the graph is
pset4/fall96.tex:and draw the directed graph
pset4/fall96sol.tex:\centerline{\psfig{figure=digraph.ps,height=2in}}
pset4/fall98sol.tex:\usepackage{graphics}
pset4/fall99.tex:Let $R$ be the lexicographic ordering of strings of symbols
pset4/fall99.tex:definition of a lexicographic order and noticing
pset4/fall99.tex:edges the graph may have is $k(v-k)$ (an edge between each pair of 
pset4/fall99.tex:These graphs are not isomorphic. The second has a vertex of degree 4,
pset4/fall99.tex:These two graphs are isomorphic. Each consists of a $K_4$ with a fifth vertex
pset4/fall99.tex:The {\em complement} of an undirected graph $G=(V,E)$ is the graph 
pset4/fall99.tex:Argue that a graph is 2-colorable if and only if every simple cycle is of
pset4/fall99.tex:Assume a graph has a simple cycle of odd length.
pset4/fall99.tex:two colors (red and blue) sufficed to color the graph containing this circuit.
pset4/fall99.tex:Therefore at least three colors are needed. Hence a graph is 2-colorable only
pset4/fall99.tex:if every simple cycle is of even length. Conversely, assume the graph has
pset4/fall99.tex:graph using two colors. Without loss of generality, assume that the 
pset4/fall99.tex:graph is connected. (As otherwise we can repeat the argument for each 
pset4/fall99.tex:connected component of the graph). Select a node, say $m$, in the graph and
pset4/fall99.tex:graph. If $u$ and $w$ are adjacent to a node in $S_{i-1}$ then we have a 
pset4/fall99sol.tex:Let $R$ be the lexicographic ordering of strings of symbols
pset4/fall99sol.tex:definition of a lexicographic order and noticing
pset4/fall99sol.tex:edges the graph may have is $k(v-k)$ (an edge between each pair of 
pset4/fall99sol.tex:These graphs are not isomorphic. The second has a vertex of degree 4,
pset4/fall99sol.tex:These two graphs are isomorphic. Each consists of a $K_4$ with a fifth vertex
pset4/fall99sol.tex:The {\em complement} of an undirected graph $G=(V,E)$ is the graph 
pset4/fall99sol.tex:Argue that a graph is 2-colorable if and only if every simple cycle is of
pset4/fall99sol.tex:Assume a graph has a simple cycle of odd length.
pset4/fall99sol.tex:two colors (red and blue) sufficed to color the graph containing this circuit.
pset4/fall99sol.tex:Therefore at least three colors are needed. Hence a graph is 2-colorable only
pset4/fall99sol.tex:if every simple cycle is of even length. Conversely, assume the graph has
pset4/fall99sol.tex:graph using two colors. Without loss of generality, assume that the 
pset4/fall99sol.tex:graph is connected. (As otherwise we can repeat the argument for each 
pset4/fall99sol.tex:connected component of the graph). Select a node, say $m$, in the graph and
pset4/fall99sol.tex:graph. If $u$ and $w$ are adjacent to a node in $S_{i-1}$ then we have a 
pset4/spring96.tex:The {\em intersection graph} of a collection of sets $A_1,A_2,...,A_n$
pset4/spring96.tex:is the graph that has a vertex for each of these sets and has an edge
pset4/spring96.tex:nonempty intersection. Construct the intersection graph for the
pset4/spring96.tex:\ppart Show that a graph is {\em simple} (cf. Rosen, \S 7.1, Def. 1) iff it
pset4/spring96.tex:is graph isomorphic (cf. Rosen, \S 7.3, Def. 1) to an intersection graph.
pset4/spring96sol.tex:\ppart ...Construct the intersection graph for the following collection
pset4/spring96sol.tex:The intersection graph of $A_1,A_2,A_3,A_4,A_5$ is
pset4/spring96sol.tex:\ppart Show that a graph is {\em simple} (cf. Rosen, \S 7.1, Def. 1) iff it
pset4/spring96sol.tex:is graph isomorphic (cf. Rosen, \S 7.3, Def. 1) to an intersection graph.
pset4/spring96sol.tex: First we prove that if a graph is simple then it is 
pset4/spring96sol.tex: graph isomorphic to an intersection graph.
pset4/spring96sol.tex: Let $(V,E)$ be a simple graph. For each vertex $v\in V$ 
pset4/spring96sol.tex: We will show that the function $f(v)=\{v\}\cup A_v$ is a graph isomorphism 
pset4/spring96sol.tex: from  $(V,E)$ to the intersection graph of 
pset4/spring96sol.tex: Consider for example a graph with two vertices
pset4/spring96sol.tex: edge and isolated from the rest of the graph.
pset4/spring96sol.tex: In order to prove that $f$ is also a graph isomorphism,
pset4/spring96sol.tex: in the intersection graph.
pset4/spring96sol.tex: in the intersection graph,
pset4/spring96sol.tex: This proves that $(V,E)$ is graph isomorphic to an 
pset4/spring96sol.tex: intersection graph.
pset4/spring96sol.tex: Conversely, assume that $(V,E)$ is graph isomorphic 
pset4/spring96sol.tex: to an intersection graph. Let $f$ be an isomorphism
pset4/spring96sol.tex: from $(V,E)$ to an intersection graph of a collection 
pset4/spring96sol.tex: graph. 
pset4/spring96sol.tex: to $f(v_1)$ in the intersection graph.
pset4/spring96sol.tex: From the definition of graph isomorpism 
pset4/spring96sol.tex: graph.  But the intersection graph by definition only has edges between
pset4/spring99.tex:\usepackage{graphics}
pset4/spring99.tex:\centerline{\resizebox{!}{2.0in}{\includegraphics{ant.eps}}}
pset4/spring99.tex:\centerline{\resizebox{!}{2.0in}{\includegraphics{lightsout.eps}}}
pset4/spring99.tex:\centerline{\resizebox{!}{2.0in}{\includegraphics{map1.eps}}}
pset4/spring99.tex:adjacent node in the graph.  We would like to organize our routes such
pset4/spring99.tex:\centerline{\resizebox{!}{2.0in}{\includegraphics{map2.eps}}}
pset4/spring99.tex:\problempart Describe a general criterion for a graph where I would be able
pset4/spring99sol.tex:\usepackage{graphics}
pset4/spring99sol.tex:\centerline{\resizebox{!}{2.0in}{\includegraphics{ant.eps}}}
pset4/spring99sol.tex:\centerline{\resizebox{!}{2.0in}{\includegraphics{lightsout.eps}}}
pset4/spring99sol.tex:\centerline{\resizebox{!}{2.0in}{\includegraphics{map1.eps}}}
pset4/spring99sol.tex:adjacent node in the graph.  We would like to organize our routes such
pset4/spring99sol.tex:graph has only even-length cycles, and hence no amount of loops attached
pset4/spring99sol.tex:every two nodes on the graph if the graph is connected and not
pset4/spring99sol.tex:bi-partite.  The graph in this example is connected but it {\em is}
pset4/spring99sol.tex:\centerline{\resizebox{!}{2.0in}{\includegraphics{map2.eps}}}
pset4/spring99sol.tex:that this graph is connected but not bipartite.  Note also that, in
pset4/spring99sol.tex:contrast to the previous graph, this one has an odd cycle.
pset4/spring99sol.tex:\problempart Describe a general criterion for a graph where I would be able
pset4/spring99sol.tex:Such graph must have an even-length path between every two nodes.  A graph
pset4/spring99sol.tex:vertices.  Since there is a path between every two vertices, the graph is
pset4/spring99sol.tex:certainly connected.  Now supppose the graph was also bipartite.  On any
pset4/spring99sol.tex:path in a bipartite graph, the successive vertices alternate colors. So if
pset4/spring99sol.tex:must have the same color, a contradiction.  Hence the graph cannot be bipartite.
pset4/spring99sol.tex:Suppose a connected graph has a pair of vertices $v \neq w$ such that
pset4/spring99sol.tex:the graph is bipartite.
pset4/spring99sol.tex:black is a 2-coloring of the graph.
pset4/spring99sol.tex:But because the graph is connected, there is also a path, $q$, from $x$ to
pset4/spring99sol.tex:So we have shown that the graph is bipartite. \qed
pset4/spring99sol.tex:Another solution to this problem was to argue that a graph has an
pset4/spring99sol.tex:A graph is bipartite if and only if it has no odd cycles.}
pset4/spring99sol.tex:To say that a graph is bipartite is the same as to say that it is
pset4/spring99sol.tex:will prove is the following: $P(n)=$``For every graph $G=(V,E)$ for
pset4/spring99sol.tex:{\em Base case:} $P(0)$ is true because a graph with no edges is both
pset4/spring99sol.tex:create a graph $G'=(V,E')$ where $E'=E\setminus\{e\}$.  Then $|E'|<n$
pset5/fall94.tex:A \defi{clique} is a graph with edges between all pairs of vertices.
pset5/fall94.tex:An \defi{independent set} is a graph with no edges.
pset5/fall94.tex:Recall from the last problem set ({\bf 4-8(b)}), that any graph on
pset5/fall94.tex:6 nodes contains (as an induced subgraph) either a clique on 3 nodes 
pset5/fall94.tex:integers $(k,\ell)$, there exists an $n$ such that every graph on $n$
pset5/fall94.tex:nodes contains (as an induced subgraph) either a clique on $k$ nodes
pset5/fall94.tex:%% 	that for any (k,l), there is some n s.t. any graph on n nodes has
pset5/fall94.tex:%% Prove that in any undirected graph there are two nodes with the same degree.
pset5/fall94sol.tex:A \defi{clique} is a graph with edges between all pairs of vertices.
pset5/fall94sol.tex:An \defi{independent set} is a graph with no edges.
pset5/fall94sol.tex:there exists an $n$ such that every graph on $n$ nodes 
pset5/fall94sol.tex:Take $n=1$.  There is only one graph possible on one node (it has no edges).
pset5/fall94sol.tex:$k=1$.  Then take $n=1$.  There is only one graph possible on one node
pset5/fall94sol.tex:$\ell=1$.  Then take $n=1$. There is only one graph possible on one node
pset5/fall94sol.tex:By the inductive hypothesis, there exists an $n_1$ such that any graph of size
pset5/fall94sol.tex:Take $n=n_1+n_2+1$.  We will show that any graph on $n$ nodes has either a 
pset5/fall94sol.tex:Take any graph on $n$ nodes and consider a node~$v$.
pset5/fall94sol.tex:the subgraph on those nodes has either an $\ell$-independent set or
pset5/fall94sol.tex:the subgraph on these nodes either has a $k$-clique or 
pset5/fall95.tex:Consider the graph above.
pset5/fall95.tex:\ppart List all the nodes in the graph along with their associated degrees.
pset5/fall95.tex:\ppart For each pair of vertices consider the number of paths of length $3$ between them and represent this data in the form of a matrix. What relationship does this matrix bear to the adjacency matrix of the graph?
pset5/fall95.tex:A graph is said to be bipartite if it is $2$-colorable. Show that every tree is bipartite. (Hint: first show that every tree has a leaf.)
pset5/fall95.tex:{\em False theorem:} If every vertex in a graph has degree at least one then the graph is connected.\\
pset5/fall95.tex:{\em False proof:} We prove the result by induction on the number of vertices. Let $P(n)$ be ``if every vertex in a graph with $n$ vertices has degree at least one then the graph is connected.''\\
pset5/fall95.tex:Base case. $P(2)$ is true since the only graph satisfying the assumption is that with two vertices and one edge between them which is easily seen to be connected.\\
pset5/fall95.tex:Inductive step. Assume $P(n)$ is true. Now, take any graph on $n$ vertices with minimum degree at least one and add a new vertex to it. By inductive hypothesis the graph on $n$ vertices is connected. Since the new vertex satisfies the assumption it must have degree at least one, so it must have an edge connecting it to one of the remaining $n$ vertices. Thus the whole graph is connected. Hence $P(n+1)$ is true. Thus, $P(n)$ is true for all $n$.
pset5/fall95.tex:%A graph is said to be planar if it can be drawn on the plane so that edges do not cross each other. Take the following fact for granted:  every planar graph contains at least one node of degree at most $5$. Now prove that any planar graph can be $6$-colored.
pset5/fall95sol.tex:is a graph consisting of vertices $v_1, v_2, \ldots, v_n$, and
pset5/fall95sol.tex:Hasse diagram of $X'$ is the graph $P_n$.
pset5/fall95sol.tex:The graph has two connected components.
pset5/fall95sol.tex:By a {\em leaf} in a graph, we mean a vertex of degree $1$.
pset5/fall95sol.tex:The ``theorem'' is in fact incorrect; consider the graph we
pset5/fall95sol.tex:induction, where we form an $(n+1)$-node graph by attaching 
pset5/fall95sol.tex:a vertex to an $n$-node graph of minimum degree at least one.  This does
pset5/fall95sol.tex:{\em not} produce all possible $(n+1)$-node graphs of minimum degree 
pset5/fall95sol.tex:and so the set of graphs for which we end up proving the theorem is
pset5/fall95sol.tex:{\em not} the set of all graphs of minimum degree at least one.
pset5/fall95sol.tex:For example, the following graph is not produced by this ``building-up''
pset5/fall95sol.tex:graph of minimum degree one --- the answer is that you can't.)
pset5/fall96.tex:Let $G$ be a graph with $v$ vertices and $e$ edges. Let $M$ be the
pset5/fall96.tex:\ppart If $G$ is a simple graph with $15$ edges and $\overline G$ has 
pset5/fall96.tex:Recall the theorem given in class that given a task graph that is a
pset5/fall96.tex:graph on page $419$ of Rosen. 
pset5/fall96.tex:\ppart Give an algorithm to determine, given an undirected graph $G$, 
pset5/fall96.tex:graph is represented by an adjacency matrix.
pset5/fall96.tex:\ppart Give an algorithm to determine, given an undirected graph $G$, 
pset5/fall96.tex:\ppart Repeat (b), but now assume that your graph is bipartite. Can you
pset5/fall96.tex:%Describe an algorithm to decide whether a graph is bipartite.
pset5/fall96.tex:An {\em independent set} of a graph $G=(V,E)$ is a subset $V'\subseteq V$ 
pset5/fall96.tex:Consider an alternative graph coloring algorithm to the one given in
pset5/fall96.tex:Given an undirected graph $G$ with degree 
pset5/fall96.tex:graph $G$ by removing all the colored vertices and their incident
pset5/fall96.tex:edges. Color the vertices of the remaining graph with the remaining
pset5/fall96.tex:colors to color any undircted graph with degree $\leq d$.
pset5/fall96.tex:others when given the opportunity. How can a graph model and a
pset5/fall96.tex:{\bf Theorem:} Given a connected graph $G=(V,E)$, where every node in
pset5/fall96.tex:the graph is associated with a positive integer, {\em i.e.},
pset5/fall96sol.tex:complete graph on $n$ vertices must have $15+13 = 28$ edges.  
pset5/fall96sol.tex:Now the complete graph on $n$ vertices has $n(n-1)/2$ edges. (One way
pset5/fall96sol.tex:\ppart Let $G=(V,E)$ be an undirected graph, where $|V|=n$. Assume $G$
pset5/fall96sol.tex:\ppart If the graph $G=(V,E)$ is bipartite, then there are two sets 
pset5/fall96sol.tex:one creates a graph with two components. The removal of any other
pset5/fall96sol.tex:vertex does not disconnect the graph.
pset5/fall96sol.tex:must not be incident on the same edge in the graph. Hence, with 
pset5/fall96sol.tex:statement that any undirected graph
pset5/fall96sol.tex:Base Case: $P(0)$ is clearly true since any graph with $0$ degree 
pset5/fall96sol.tex:is $1$-colorable. $P(1)$ is also true since any graph with degree 
pset5/fall96sol.tex:Let $G$ be any undirected graph with
pset5/fall96sol.tex:always exists: if the graph is complete, an $MIS$ consists of only one
pset5/fall96sol.tex:node in the graph).  Color all the vertices in $V'$ using the same 
pset5/fall96sol.tex:color. Now reduce the graph by removing all the vertices in $V'$ and their
pset5/fall96sol.tex:reduced graph has degree $\leq d$, and thus by the induction
pset5/fall96sol.tex:color $V'$ to the set of $\leq {d+1}$ colors, implies that graph $G$ 
pset5/fall96sol.tex:We let the vertices of a graph be the animals, and we draw an edge
pset5/fall96sol.tex:graph gives an assignment of habitats, where the colors are the
pset5/fall96sol.tex:Suppose that not all the nodes in the graph have the same value.
pset5/fall96sol.tex:the graph. Consider a node $v$ with value $s$. This node is connected
pset5/fall96sol.tex:smallest value in the graph, and $G$ is connected. But this 
pset5/fall96sol.tex:Hence, in a connected graph if the value of 
pset5/fall98sol.tex:\usepackage{graphics}
pset5/fall99.tex:model knight's tours using the graph that has a vertex for each square
pset5/fall99.tex:the corresponding graph. 
pset5/fall99.tex:Show that the graph representing the legal moves of a
pset5/fall99.tex:partitions the vertex set of the graph representing the legal moves of
pset5/fall99.tex:or $-1-2=-3$. Therefore every edge in this graph joins a vertex in $A$
pset5/fall99.tex:to a vertex in $B$. Thus the graph is bipartite.}
pset5/fall99.tex:part (b), the corresponding graph is bipartite, from PS 4, problem 7,
pset5/fall99.tex:directed multigraph having no isolated vertices has an Eulerian
pset5/fall99.tex:circuit if and only if the graph is weakly connected and the in-degree
pset5/fall99.tex:\solution{First suppose that the directed multigraph has an Euler
pset5/fall99.tex:other vertex, the graph must be strongly connected (and hence also
pset5/fall99.tex:degrees are equal for each vertex. Conversely, suppose that the graph
pset5/fall99.tex:A \textbf{directed, rooted spanning tree} of a digraph is a
pset5/fall99.tex:rooted tree whose edges are from the digraph with the property 
pset5/fall99.tex:the digraph is reachable by a directed path from the root of the tree.
pset5/fall99.tex:a connected directed graph in which each vertex has the same in-degree
pset5/fall99.tex:directed graph. We follow $C$ and delete from the directed graph every
pset5/fall99.tex:Let $T_1$ and $T_2$ be spanning trees of a graph. The
pset5/fall99.tex:$T_1, T_2$ and $T_3$ are spanning trees of the simple graph $G$. Show
pset5/fall99.tex:A minimum spanning tree in a connected weighted graph $G$ is a
pset5/fall99.tex:in a connected weighted graph must be part of any minimum spanning
pset5/fall99.tex:$e$. If we add $e$ to $T$, then we will obtain a graph with exactly
pset5/spring95.tex:Let $G = (V,E)$ be an undirected graph.  Define the {\it line graph}
pset5/spring95.tex:$G' = (E,E')$ as the graph whose vertices are the edges of $G$, and
pset5/spring95.tex:Define the graph $G=(V,E)$ where $E=E_1\cup E_2$.
pset5/spring95sol.tex:Let $G = (V,E)$ be an undirected graph.  Define the {\it line graph}
pset5/spring95sol.tex:$G' = (E,E')$ as the graph whose vertices are the edges of $G$, and
pset5/spring95sol.tex:N(e)$ in graph $G'$, then $e_i$ and $e$ share an endpoint in $G$. That is,
pset5/spring95sol.tex:Define the graph $G=(V,E)$ where $E=E_1\cup E_2$.
pset5/spring95sol.tex:color it $(c_1, c_2)$ in graph $G$ if it is colored $c_1$ in $G_1$ 
pset5/spring95sol.tex:of colors used:  Figure 1 depicts the graph 
pset5/spring95sol.tex:$K_4$ (the complete graph on $4$ vertices),
pset5/spring95sol.tex:\caption{An example of a non 3-colorable graph that is union of two trees. }
pset5/spring96.tex:% graph non-isomorphism
pset5/spring96.tex:In last tutorial you have seen that the two graphs
pset5/spring96.tex:Both graphs have eight vertices and are 
pset5/spring96.tex:3-regular (a graph is 3-regular iff
pset5/spring96.tex:Give another 3-regular connected simple graph with eight vertices
pset5/spring96.tex:either of the above graphs,
pset5/spring96.tex:3-regular connected simple graph with 8 vertices.
pset5/spring96.tex:{\bf Note}: All graphs must be connected and simple, i.e.,
pset5/spring96.tex:%graph isomorphism
pset5/spring96.tex:The simple graphs $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ 
pset5/spring96.tex:\ppart Show that if two simple graphs are graph-isomorphic
pset5/spring96.tex:\ppart Give a easy example of two simple graphs 
pset5/spring96.tex: that are edge-isomorphic but not graph-isomorphic.
pset5/spring96.tex:property of graphs such that if a graph has the peculiar property, then it
pset5/spring96.tex:is edge-isomorphic but non-graph-isomorphic to another graph.  Moreover,
pset5/spring96.tex:Theorem: Two simple graphs without the peculiar property are
pset5/spring96.tex:edge-isomorphic if and only if they are graph-isomorphic.
pset5/spring96.tex:% graph connectivity
pset5/spring96.tex:Consider a directed graph $G$ 
pset5/spring96.tex:formulated as finding a particular kind of path in the graph $G$.
pset5/spring96.tex:\ppart Let $d$ be the maximum degree of any vertex in a graph $G$.  Show
pset5/spring96.tex:the graph is finite.)
pset5/spring96.tex:graphs such that the number of edges in $G_{n}$ is $O(f(n))$.  Show that
pset5/spring96sol.tex:% graph non-isomorphism
pset5/spring96sol.tex:graphs with 8 vertices. Figure~\ref{fig:graphs} shows all five
pset5/spring96sol.tex:\caption{All five non-isomorphic, connected, 3-regular graphs with 8 vertices.}
pset5/spring96sol.tex:\label{fig:graphs}
pset5/spring96sol.tex:Each of the graphs has a unique features (listed under the graph) not
pset5/spring96sol.tex:present in the other graphs. However, we have not been able to come up
pset5/spring96sol.tex:%graph isomorphism
pset5/spring96sol.tex:The simple graphs $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ are {\em
pset5/spring96sol.tex:Show that if two simple graphs are graph-isomorphic then they are also
pset5/spring96sol.tex:Suppose $G_1$ and $G_2$ are graph-isomorphic.  Then, there exists a
pset5/spring96sol.tex:undirected graph, the edges $(a,b)$ and $(b,a)$ are considered to be
pset5/spring96sol.tex:always an edge in $G_2$, since $f$ is a graph isomorphism and
pset5/spring96sol.tex:Give a easy example of two simple graphs that are edge-isomorphic but
pset5/spring96sol.tex:not graph-isomorphic.
pset5/spring96sol.tex:Let $G_1$ is the empty graph (i.e. no nodes or edges), and let $G_2$
pset5/spring96sol.tex:be a single node with no edges.  These two graphs are edge-isomorphic,
pset5/spring96sol.tex:but not graph-isomorphic.  The edge-isomorphism is vacuous, since
pset5/spring96sol.tex:There is an easily characterized ``peculiar'' property of graphs such
pset5/spring96sol.tex:that if a graph has the peculiar property, then it is edge-isomorphic
pset5/spring96sol.tex:but non-graph-isomorphic to another graph.  Moreover,
pset5/spring96sol.tex:{\bf Theorem:} Two simple graphs without the peculiar property are
pset5/spring96sol.tex:edge-isomorphic if and only if they are graph-isomorphic.
pset5/spring96sol.tex:edges).  Two graphs could be edge isomorphic, but have a different
pset5/spring96sol.tex:graph-isomorphic).
pset5/spring96sol.tex:{\bf Theorem:} Two graphs without any isolated nodes are
pset5/spring96sol.tex:edge-isomorphic if and only if they are graph-isomorphic.
pset5/spring96sol.tex:creates a graph-isomorphism.
pset5/spring96sol.tex:% graph connectivity
pset5/spring96sol.tex:Consider a directed graph $G$ where the vertices are all possible
pset5/spring96sol.tex:can be formulated as finding a particular kind of path in the graph
pset5/spring96sol.tex:two letters of the second word.  Thus, given a path in the graph, we
pset5/spring96sol.tex:corresponds to a edge in the graph.  Therefore, if we can find an
pset5/spring96sol.tex:\ppart Let $d$ be the maximum degree of any vertex in a graph $G$.  Show
pset5/spring96sol.tex:the graph is finite.)
pset5/spring96sol.tex:The proof is by induction on $n$, the number of vertices in the graph $G$.
pset5/spring96sol.tex:$v_1,\dots,v_{n+1}$. Consider the subgraph $G'$ of $G$ obtained from
pset5/spring96sol.tex:graphs such that the number of edges in $G_{n}$ is $O(f(n))$.  Show that
pset5/spring96sol.tex:Let $G_n$ be the graph in the sequence, and assume $n$ is large enough
pset5/spring96sol.tex:distinct colors. The rest of the graph has vertices of degree less
pset5/spring99.tex:\usepackage{graphics}
pset5/spring99sol.tex:\usepackage{graphics}
pset6/fall98sol.tex:\usepackage{graphics}
pset6/fall99.tex:%\usepackage{graphics}
pset6/fall99sol.tex:%\usepackage{graphics}
pset6/spring94.tex:How many edges are possible in an undirected graph on $n$ nodes?
pset6/spring94.tex:How many undirected graphs are possible on $n$ nodes?
pset6/spring94.tex:$E_1=\{(1,2)\}$ and $E_2=\{(1,3)\}$ are different graphs.)
pset6/spring94.tex:%% 	that for any (k,l), there is some n s.t. any graph on n nodes has
pset6/spring94.tex:We will illustrate graphically the application 
pset6/spring99.tex:\usepackage{graphics}
pset6/spring99sol.tex:\usepackage{graphics}
pset6/spring99sol.tex:\usepackage{graphics}
pset7/fall94.tex:How many edges are possible in an undirected graph on the set
pset7/fall94.tex:$V_n=\set{1,2,\ldots,n}$ of vertices?  How many undirected graphs are
pset7/fall94.tex:different graphs.
pset7/fall94sol.tex:\problem {\bf Undirected graphs}
pset7/fall94sol.tex:In an undirected graph on $n$ vertices, an edge is an unordered pair of
pset7/fall94sol.tex:possible undirected graphs on $n$ vertices.
pset7/fall98.tex:\usepackage{graphics}
pset7/fall98sol.tex:\usepackage{graphics}
pset7/fall99.tex:\usepackage{amsmath,graphicx}
pset7/fall99.tex:        \includegraphics[width=2.5in]{H40-ps7-fig3}
pset7/fall99.tex:        \includegraphics[width=2.5in]{H40-ps7-fig2}
pset7/fall99.tex:          \includegraphics[width=2.5in]{H40-ps7-fig1}
pset7/fall99sol.tex:\usepackage{amsmath,graphicx}
pset7/fall99sol.tex:\includegraphics[width=2.5in]{H40-ps7-fig3}
pset7/fall99sol.tex:\includegraphics[width=2.5in]{H40-ps7-fig2}
pset7/fall99sol.tex:\includegraphics[width=2.5in]{H40-ps7-fig1}
pset7/spring96.tex:\problem How many ways are there to colour the vertices of the graph below
pset7/spring96sol.tex:\problem How many ways are there to colour the vertices of the graph below
pset7/spring96sol.tex:The above graph can be colored with either 3 or 4 colors.  With 4 colors,
pset7/spring98.tex:How many ways can a photographer at a wedding arrange 5
pset7/spring98sol.tex:How many ways can a photographer at a wedding arrange 5
pset7/spring99.tex:\usepackage{graphics}
pset7/spring99.tex:\centerline{\resizebox{2.0in}{!}{\includegraphics{diamond.eps}}}
pset7/spring99.tex:\problem {\bf (15 points) } Let $G$ be a simple, undirected graph with
pset7/spring99sol.tex:\usepackage{graphics}
pset7/spring99sol.tex:\centerline{\resizebox{2.0in}{!}{\includegraphics{diamond.eps}}}
pset7/spring99sol.tex:\problem {\bf (15 points) } Let $G$ be a simple, undirected graph with
pset8/fall95.tex:Construct a graph that has one vertex for each legal configuration of
pset8/fall95.tex:reversible we can see that the graph is undirected. Show that this
pset8/fall95.tex:graph contains a connected component of size less than that of part a)
pset8/fall96.tex:How many edges are possible in an undirected graph on the set
pset8/fall96.tex:$V_n=\set{1,2,\ldots,n}$ of vertices?  How many undirected graphs are
pset8/fall96.tex:different graphs.
pset8/fall96sol.tex:\problem {\bf Undirected graphs}
pset8/fall96sol.tex:In an undirected graph on $n$ vertices, an edge is an unordered pair of
pset8/fall96sol.tex:possible undirected graphs on $n$ vertices.
pset8/fall97.tex:How many ways can a photographer at a wedding arrange 6
pset8/fall97sol.tex:How many ways can a photographer at a wedding arrange 6
pset8/fall98sol.tex:\usepackage{graphics}
pset8/fall99.tex:\usepackage{graphics}
pset8/fall99.tex:work with other people as a graph coloring problem ?
pset8/fall99.tex:This can be represented as a graph with nodes representing
pset8/fall99.tex:a company to a person. Thus your graph could look like :
pset8/fall99.tex:\centerline{\resizebox{!}{1.5in}{\includegraphics{ps5-p5.eps}}}
pset8/fall99.tex:The graph can be colored using either 4 colors or 3 colors. 
pset8/fall99.tex:You have to figure out the number of ways to color the graph
pset8/fall99.tex:Then the number of possible ways to color the graph using 3
pset8/fall99sol.tex:\usepackage{graphics}
pset8/fall99sol.tex:work with other people as a graph coloring problem ?
pset8/fall99sol.tex:This can be represented as a graph with nodes representing
pset8/fall99sol.tex:Recall that a legal graph coloring does
pset8/fall99sol.tex:of the graph would imply an assignment of people to jobs respecting
pset8/fall99sol.tex:Thus your graph could look like :
pset8/fall99sol.tex:\centerline{\resizebox{!}{1.5in}{\includegraphics{H58-p5.eps}}}
pset8/fall99sol.tex:the possible colorings of the graph that exist. 
pset8/fall99sol.tex:There are 4 nodes, thus it is possible for the graph to be
pset8/fall99sol.tex:The graph can also be colored with 3 colors.  This is because
pset8/fall99sol.tex:graph with 3 colors, from $n$ possible colors equals $P(n,3)=n!/(n-3)!$.
pset8/fall99sol.tex:The graph can not be colored with fewer colors due to the constraints
pset8/spring97.tex:Draw a conflict graph for these meetings, and schedule them 
pset8/spring97.tex:\problem Give the adjacency matrix of the graph $W_4$.  How many
pset8/spring97.tex:{\em False theorem:} If every vertex in a graph has degree at least one then the graph is connected.\\
pset8/spring97.tex:{\em False proof:} We prove the result by induction on the number of vertices. Let $P(n)$ be ``if every vertex in a graph with $n$ vertices has degree at least one then the graph is connected.''\\
pset8/spring97.tex:Base case. $P(2)$ is true since the only graph satisfying the assumption is that with two vertices and one edge between them which is easily seen to be connected.\\
pset8/spring97.tex:Inductive step. Assume $P(n)$ is true. Now, take any graph with $n$
pset8/spring97.tex:it. By inductive hypothesis the graph on $n$ vertices is
pset8/spring97.tex:the remaining $n$ vertices. Thus the whole graph is connected. Hence
pset8/spring97.tex:about graphs that that can be colored with two colors.  These graphs
pset8/spring97.tex:A graph is bipartite if and only if it contains no cycles of odd
pset8/spring97.tex:It is enough to prove this theorem for a connected graph, because then
pset8/spring97.tex:we can apply it separately to each component of an arbitrary graph.
pset8/spring97.tex:\problem Prove that a graph contains an odd-length circuit if and only
pset8/spring97.tex:\problem Suppose $G$ is a connected graph with no odd cycles (or
pset8/spring97.tex:\problemopt Suppose we are in a connected maze (undirected graph) and
pset8/spring97sol.tex:Draw a conflict graph for these meetings, and schedule them 
pset8/spring97sol.tex:The conflict graph is like the complete graph on these vertices, except it
pset8/spring97sol.tex:for a valid graph coloring of the conflict graph.
pset8/spring97sol.tex:connected by an edge in the conflict graph.  So no two of them can be
pset8/spring97sol.tex:colored the same color.  Thus coloring the conflict graph requires at least
pset8/spring97sol.tex:5 colors.  The graph can, in fact, be colored with 5 colors by giving each
pset8/spring97sol.tex:are $C_4$ and $C_5$, and they are not adjacent in the conflict graph.
pset8/spring97sol.tex:\problem Give the adjacency matrix of the graph $W_4$.  How many
pset8/spring97sol.tex:Let $F$ be the graph that results when $(u,v)$ is deleted from $T$.
pset8/spring97sol.tex:and still have $u$ have degree at least 2 in the resulting graph.  Since
pset8/spring97sol.tex:this does not create cycles, this graph is a forest.  Thus the component
pset8/spring97sol.tex:in this graph, so the simple path contains $(u,v)$.  This simple path is
pset8/spring97sol.tex:in the new graph at least $k - 1$ leaves.
pset8/spring97sol.tex:{\em False theorem:} If every vertex in a graph has degree at least one then the graph is connected.\\
pset8/spring97sol.tex:{\em False proof:} We prove the result by induction on the number of vertices. Let $P(n)$ be ``if every vertex in a graph with $n$ vertices has degree at least one then the graph is connected.''\\
pset8/spring97sol.tex:Base case. $P(2)$ is true since the only graph satisfying the assumption is that with two vertices and one edge between them which is easily seen to be connected.\\
pset8/spring97sol.tex:Inductive step. Assume $P(n)$ is true. Now, take any graph with $n$
pset8/spring97sol.tex:it. By inductive hypothesis the graph on $n$ vertices is
pset8/spring97sol.tex:the remaining $n$ vertices. Thus the whole graph is connected. Hence
pset8/spring97sol.tex:graph with $n+1$ vertices, a vertex is added to a pre-existing graph of $n$
pset8/spring97sol.tex:vertices.  It is not true however, that any $n$-subgraph of a graph with $n+1$ 
pset8/spring97sol.tex:Consider for example the graph of $4$ vertices consisting of two disjoint 
pset8/spring97sol.tex:about graphs that that can be colored with two colors.  These graphs
pset8/spring97sol.tex:A graph is bipartite if and only if it contains no cycles of odd
pset8/spring97sol.tex:It is enough to prove this theorem for a connected graph, because then
pset8/spring97sol.tex:we can apply it separately to each component of an arbitrary graph.
pset8/spring97sol.tex:\problem Prove that a graph contains an odd-length circuit if and only
pset8/spring97sol.tex:If a graph contains an odd-length cycle, then obviously it contains an 
pset8/spring97sol.tex:Now suppose that the graph contains an odd-length circuit, and consider an
pset8/spring97sol.tex:\problem Suppose $G$ is a connected graph with no odd cycles (or
pset8/spring97sol.tex:\problemopt Suppose we are in a connected maze (undirected graph) and
pset8/spring99.tex:\usepackage{graphics}
pset8/spring99.tex:Show that any set of finite digraphs, no two of which are isomorphic to
pset8/spring99.tex:\solution{Let's define an \emph{integer digraph} to be a digraph whose
pset8/spring99.tex:\in \naturals$.  Every finite digraph is obviously isomorphic to an
pset8/spring99.tex:integer digraph.  So if $A$ is some set of finite digraphs no two of which
pset8/spring99.tex:all integer digraphs.  Hence, if we show that $D$ is countable, it will
pset8/spring99.tex:digraphs with $n$ vertices.  But each graph in $D_n$ can be uniquely
pset8/spring99.tex:is some set of finite digraphs, no two of which are isomorphic to each
pset8/spring99.tex:digraph with its adjacency matrix.  If no two digraphs in $D'$ are
pset8/spring99.tex:\usepackage{graphics}
pset8/spring99.tex:Show that any set of finite digraphs, no two of which are isomorphic to
pset8/spring99.tex:\solution{Let's define an \emph{integer digraph} to be a digraph whose
pset8/spring99.tex:\in \naturals$.  Every finite digraph is obviously isomorphic to an
pset8/spring99.tex:integer digraph.  So if $A$ is a set of finite digraphs no two of
pset8/spring99.tex:integer digraphs.  Hence, if we show that the set of all integer
pset8/spring99.tex:digraphs is countable, it will follow that $A$ is countable.
pset8/spring99.tex:To show that the set of all integer digraphs is countable, let $D_n$
pset8/spring99.tex:the set of all integer digraphs with $n$ vertices.  But each graph in
pset8/spring99.tex:digraphs is $\bigcup_{n
pset8/spring99sol.tex:\usepackage{graphics}
pset8/spring99sol.tex:Show that any set of finite digraphs, no two of which are isomorphic to
pset8/spring99sol.tex:\solution{Let's define an \emph{integer digraph} to be a digraph whose
pset8/spring99sol.tex:\in \naturals$.  Every finite digraph is obviously isomorphic to an
pset8/spring99sol.tex:integer digraph.  So if $A$ is some set of finite digraphs no two of which
pset8/spring99sol.tex:all integer digraphs.  Hence, if we show that $D$ is countable, it will
pset8/spring99sol.tex:digraphs with $n$ vertices.  But each graph in $D_n$ can be uniquely
pset8/spring99sol.tex:is some set of finite digraphs, no two of which are isomorphic to each
pset8/spring99sol.tex:digraph with its adjacency matrix.  If no two digraphs in $D'$ are
pset9/fall97.tex:%graph with the following bizarre property: for every set of $k$ people
pset9/fall98sol.tex:\usepackage{graphics}
pset9/fall98sol.tex:\centerline{\resizebox{!}{3.0in}{\includegraphics{Sol9-pigfind.eps}}}
pset9/fall98sol.tex:\centerline{\resizebox{!}{1.5in}{\includegraphics{Sol9-set1.eps}}}
pset9/fall98sol.tex:\centerline{\resizebox{!}{1.5in}{\includegraphics{Sol9-set2.eps}}}
pset9/fall98sol.tex:\centerline{\resizebox{!}{3.0in}{\includegraphics{Sol9-prisoner.eps}}}
pset9/fall99.tex:%\usepackage{graphics}
pset9/fall99.tex:\problem We consider simple graphs with $n$ distinctly labeled vertices.
pset9/fall99.tex:How many complete graphs are there on these $n$ vertices?
pset9/fall99.tex:of length $i$ are there in the complete graph
pset9/fall99.tex:complete graph all vertices are connected by an edge, so the number of
pset9/fall99.tex:complete graph?  (A simple cycle is a ``circular'' simple
pset9/fall99.tex:How many such distinctly labelled $n$-vertex graphs are there?
pset9/fall99.tex:graph or not.
pset9/fall99sol.tex:%\usepackage{graphics}
pset9/fall99sol.tex:\problem We consider simple graphs with $n$ distinctly labeled vertices.
pset9/fall99sol.tex:How many complete graphs are there on these $n$ vertices?
pset9/fall99sol.tex:of length $i$ are there in the complete graph
pset9/fall99sol.tex:complete graph all vertices are connected by an edge.  A path of length
pset9/fall99sol.tex:complete graph?  (A simple cycle is a ``circular'' simple
pset9/fall99sol.tex:How many such distinctly labelled $n$-vertex graphs are there?
pset9/fall99sol.tex:graph or not.
pset9/spring94.tex:n}p^n(1-p)^{n+1}.$ Draw a graph of $f(p)$ versus $p$ and show that
pset9/spring97.tex:\problem For a simple undirected graph with edges $e_1,\ldots,e_m$,
pset9/spring97.tex:a spanning forest of the input graph.  (Hint: it may help to consider
pset9/spring97.tex:the graphs consisting of the edges $e_1,\ldots,e_k$ for various values
pset9/spring97.tex:\problem Consider the following state machine on a graph
pset9/spring97.tex:what kinds of bipartite graphs is it possible to reach a state in
pset9/spring97sol.tex:Consider the graph $(N,E)$ whose nodes are the 22 teams,
pset9/spring97sol.tex:The total number of edges in the graph is $(22\cdot 14)/2 = 154$.
pset9/spring97sol.tex:Since the degree of each node is even, the graph has 
pset9/spring97sol.tex:\problem For a simple undirected graph with edges $e_1,\ldots,e_m$,
pset9/spring97sol.tex:a spanning forest of the input graph.  (Hint: it may help to consider
pset9/spring97sol.tex:the graphs consisting of the edges $e_1,\ldots,e_k$ for various values
pset9/spring97sol.tex:\problem Consider the following state machine on a graph
pset9/spring97sol.tex:graphs do not have odd length cycle.
pset9/spring97sol.tex:what kinds of bipartite graphs is it possible to reach a state in
pset9/spring97sol.tex:for connected graphs the state machine can 
pset9/spring99.tex:\usepackage{graphics}
pset9/spring99sol.tex:\usepackage{graphics}