Unless otherwise stated, all graphs are always non-empty,
finite and
simple (i.e., without loops and multiple edges).
Every time we say “show, list, find…” we mean “prove.”
That often includes proving that what you have found or
listed is ALL
that can be found or listed.
All assignments
starting with A3 need to be typeset in LaTeX. Here are some basic guidelines:
(1) You need to leave at least 3 inch right
margin for my remarks
(2) Please leave at least 1 inch between
problems for my remarks
(3) Remember to use math mode for all math
expression, even a single letter (like x
or G)
(4) Print your assignments double sided! Save
the trees!!
Assignment LaTeX
template source and sample pdf based on Neng’s design
Assignment LaTeX
template source and sample pdf based on Sarah’s design
Assignment 9 due on Monday, 3/26 at 4 PM
Section 7.1
Problem 4
Section 7.2
Problem 2 (c)
Section 7.3
Problem 3 (c)
Problem 5 (a) (e)
Preliminary Assignment 9
Section 7.1
Problem 4
Section 7.2
Problem 2 (c)
Section 7.3
Problem 3 (c)
Problem 5 (a) (e)
Preliminary list of assignments. It will be updated every
week.
Assignment 0
Section 1.3
Problems 2 3 4
Section 1.4
Problem 2 9 11
Section 1.5
Problem 2
Assignment 1
Section 1.4
Problems 3 8
Section 1.5
Problem 3abc 4b
Section 1.6
Problem 12
Assignment 2
Section 1.4
Problem 6
Section 1.6
Problem 5
Two other problems
are here.
Assignment 3
Problem A3.1
Prove Theorem 2.5 using a proof different from the proof in the book.
Section 2.1
Problems 3 7 8
Assignment 4
Section 2.3
Problems 3 (too easy) 4a 5
Section 2.6
Problem 1
Assignment 5
Section 3.1
Problems 4 9d (possibly also b as a bonus problem)
Section 3.3
Problems 3
Two other problems
are here.
Assignment 6
Section 3.3
Problems 5 (for definition of Qn see page 16) 7 9 10 14
Assignment 7
Section 4.1
Problems 7 8 (we are asking here in how many ways you can select a perfect matching)
Section 4.2
Problems 4ab (e is too difficult)
Section 6.5
Problem 3 4
Assignment 8
Section 5.2
Problems 6 8 11
Section 5.4
Problem 5 Give reasons!
Section 6.1
Problem 5 6 (In 5 you need to add the assumption that G is connected, otherwise it’s not true) 7 not used, saved for PP
Assignment 9
Section 7.1
Problem 4
Section 7.2
Problem 2 (c)
Section 7.3
Problem 3 (c)
[Problem 5 (a) (e)]
List of old assignments.
Assignment 5
Section 3.3
Problems 5 (for definition of Qn see page 16)
Section 4.1
Problems 7 8 9 (9 unused)
Section 4.2
Problem 4 (a) (b) only (unused)
Assignment 6
Section 5.2
Problem 6 8
Section 5.4
Problems 5 6 In both problems give reasons!
Assignment 7
Section 6.1
Problems 5 6 (In 5 you need to add the assumption that G is connected, otherwise it’s not true) none used
Section 6.5
Problem 3 4
Assignment 8
Section 7.1
Problem 4
Section 7.2
Problem 2 (c) 3
Section 7.3
Problem 3 (c)
[Problem 5 (a) (e)]
OLD ASSIGNMENTS
These are assignments from one of my previous classes. Many
of them will be used again. A current assignment will always be posted at the
top of this page.
Section 1.4
Problems 3 4 6 8
Section 1.5
Problem 3
Section 1.6
Problem 12
Section 2.1
Problems 6 a b c 8
Section 2.2
Problem 4
Section 2.3
Problem 4 a
You can replace one or two of the assignment problems by
solving two or four of the following problems (that means replacing each
original problem by two new, easier ones):
1.4.10
1.4.11
1.6.13
2.1.1 (just trees with 7 vertices)
Problem A3.1
Let T be a tree and the center of T be the set of all vertices of T with eccentricity equal to the radius of T . Prove that the center consists either of one vertex or of two adjacent vertices.
Problem A3.2
What is the number of edges in an acyclic graph with n vertices and k components? Prove your result in two different ways.
Problem A3.3
Let P and Q be two longest paths in a connected graph G. Show that they have a common vertex.
Problem A3.4
Find the cheapest spanning tree of a graph. You will get the graph in class on Friday
Section 2.6
Problem 5
Section 3.3
Problems 5 14 (Problem 2 is extra bonus problem worth additional 10%)
Section 4.1
Problem 6
Section 5.2
Problem 5
Section 5.4
Problems 5 6
Section 6.1
Problem 6
Problem A6.1
Let R(4,1,2,2) be ca caterpillar with the spine containing vertices a,b,c,d and edges ab,bc,cd.
Let deg a = 5, deg b = 3, deg c = 4, deg d = 3. This means that a has 4 neighbors of degree 1, b has 1 neighbor of degree 1, c has 2 neighbors of degree 1, and d has 2 neighbors of degree 1.
Find at least two different graceful labelings of R(4,1,2,2). For each additional labeling there will be a small bonus.
Problem A6.2
Prove that the one 1-factorizations of the complete graph with 6 vertices we have constructed in class are isomorphic. Call these factorizations F and G. You need to show the mapping that will take each factor from F onto a factor from G. Remember that F is the "1-rotational" factorization and G is the "bipartite" one.
Problem A6.3
Find three different 1-factorizations of the complete graph on 8 vertices and prove they are non-isomorphic.
Problem A6.4
Find a graceful labeling of a double-kite. This is a graph with 10 vertices and 11 edges consisting of two 4-cycles, joined by a path of length 3.
Problem A6.BONUS
Find a general method for graceful labelings of lobsters. A lobster is a tree which after removal of all vertices of degree one becomes a caterpillar. A caterpillar is a tree that after removal of all vertices of degree one becomes a path or an isolated vertex.
Use next time
problems from 2006 Assig 5 problem 4.10 and Assig 3 problem 1
Assignment 1
Section 1.4
Problems 3 8
Section 1.5
Problem 3
Section 1.6
Problem 12
Assignment 2
Section 1.4
Problem 6
Section 1.6
Problem 5
Two other problems
are here.
Assignment 3
Problem A3.1
Prove Theorem 2.5 using a proof different from the proof in the book.
Section 2.1
Problems 3 7 8
Assignment 4
Section 3.1
Problem 4
Section 3.3
Problems 3 5 7
Assignment 5
Section 4.1
Problems 8 9
Section 5.2
Problem 8
Problem A5.1
Characterize completely all planar complete multipartite
graphs (in other words, list all of them).