Problem 0-1
Show that the Gale-Shapley algorithm with $n$ men and $n$ women always terminates in at most $n^2$ rounds.
Problem 0-2
TRUE of FALSE? If G is a connected weighted graph, then every minimum cost edge appears in every minimum spanning tree.
Problem 0-3
Suppose that $G$ is a disconnected graph. Explain how the Matrix tree theorem could be used to show that $G$ has 0 spanning trees.
Problem 0-4
TRUE of FALSE? If G is a connected weighted simple graph with distinct edge costs, then the minimum spanning tree must contain the two smallest cost edges.
Problem 0-6
Suppose two men in the Gale-Shapley algorithm have identical lists of preferences. Do they always appear simultaneously in the same woman's room until the last round?
Problem 0-7
Prove that any tree has at least 2 leaves.
Problem 1-1
Let G be the graph of the tic-tac-toe board: 12 vertices, 12 edges, it looks like a #.
(a) How many vertices of G have degree equal to 1?
(b) Find an edge of G so that if you delete that edge, the remaining graph is a tree.
(c) How many faces does G have? Verify Euler's formula for G.
(d) What is the minimum number of edges you need to add to G so that the new graph has an Eulerian cycle? (You do not get to add any more vertices.)
(e) Is G a bipartite graph?
Problem 1-2
Which trees have an Eulerian path?
Problem 1-3
How many edges does a connected graph on n vertices have if the graph has a unique cycle?
Problem 1-4
How many labeled trees with $n$ vertices have two vertices of degree $n-2$?
Problem 1-5
Let A be the adjacency matrix for the complete bipartite graph $K_{2,3}={1,2} \cup \{A,B,C\}.$ What is the 1A-entry of $A^{136}?$
Problem 1-6
Find a weighted graph, whose edges have distinct costs, and whose minimum spanning tree contains an edge of maximum cost.
Problem 1-7
Let G be the graph K5 with a single edge removed. Draw a planar representation of G, and verify Euler's formula for G.
Problem 1-8
Explain in your own words why there are exactly 5 solutions to the equation $1/p+1/q=1/2+1/E$, where p,q, and E are positive integers, all at least three.
Problem 1-9
Show that it is impossible to have a graph which has 5 vertices of degree 3, 2 vertices of degree 4, and 1 vertex of degree 6.
Problem 1-10
Suppose that a certain planar graph G has 13 faces:12 triangles and 1 square. Find the number of edges in G. Then use Euler's formula to find the number of vertices in G.
Problem 1-11
Which of the complete bipartite graphs Kn,m have an Eulerian circuit?
Problem 1-12
Show that if a tree has 5 vertices, the sum of the vertex degrees must be 8. Then give an example of a tree with 5 vertices whose vertex degrees are 3,2,1,1,1.
Problem 1-13
Explain, in your own words, the argument using Euler's formula which proved that K3,3 was not planar.
Problem 1-14
Suppose that a graph G has 3 connected components, each of which is a tree. If G has 14 vertices, how many edges does G have?
Problem 1-15
Draw a planar representation of the complete bipartite graph K2,4. How many faces does your planar graph have? Does Euler's formula hold?
Problem 1-16
A soccer ball is a polyhedron consisting of 20 hexagons and 12 pentagons. The polyhedron can be drawn as a planar graph. There are 60 vertices, each of degree 3. How many edges does the soccer ball have?
Problem 1-17
Show that it is impossible to have a planar graph, all of whose faces are hexagons, with each vertex degree at least 3.