Problem Set VI, for Wednesday, May 13

Mathematics 61, section 1

Representation of Graphs:

• 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:

• 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:

• Exercise 5.
• Exercise 7.

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.