Problem Set VI, for Friday, November 16

Mathematics 61

Representation of Graphs (page 228 in Discrete Source or page 355 in Discrete Mathematics):

• Exercises 6 and 12.   You will need to choose orderings.
• Exercise 14.
• Exercise 21.   Note that #14 is an example.   Since A is symmetric, we may suppose that if A' is a
  p x q matrix, then A'' is a q x p matrix.
• Exercise 23.   You may assume the graph is simple.

Isomorphisms of Graphs (page 234 in Discrete Source or page 361 in Discrete Mathematics):

• Exercise 3.
• Exercise 5.
• Exercise 22.   Also say exactly how many of these graphs there are, up to isomorphism.   (In other words, we want to determine how many equivalence classes result from partitioning the set of simple 4-vertex graphs by the isomorphism relation.)
• Exercise 28.   This problem does not deserve a star.   If a simple graph is not connected, then there is a short path in the complement between two vertices.

Planar Graphs (page 240 in Discrete Source or page 367 in Discrete Mathematics):

• Exercise 5.
• Exercise 7.
• Exercise 16, but assume that G has exactly eleven vertices.   (Then the problem does not require a star.   Suggestion: See Exercise 13, which will be done in class.)
• Exercise 23.

Formula Summary for Graphs. Here G is a finite graph,
v   is the number of vertices,
e   is the number of edges,
k   is the number of components, and
f   is the number of faces (if G is planar).

1.       v is less than or equal to e + k
for any G.   Equality holds if and only if G is acyclic.

2.       v + f = e + k + 1
if G is planar.

3.       e is less than or equal to 3v - 6
if G is planar, simple, and v is at least 3.

4.       e is less than or equal to 2v - 4
if G is planar, simple, v is at least 4, and G has no K_3 subgraph.

Click here for answers in .pdf format.