Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

Here are the /Solutions.

# 1. Graph products

Recall that the square product G◻H of two graphs G and H has vertex set VG×VH and edge set {(u,u')(v,v'): u=v and u'v'∈EH or uv∈EG and u'=v'}, while the cross product G×H has the same vertex set but edge set {(u,u')(v,v'): uv∈EG and u'v'∈EH}.

Suppose that between any two vertices in G there is a path of length at most m and between any two vertices in H there is a path of length at most n.

1. Prove or disprove: Between any two vertices in G◻H there is a path of length at most m+n.
2. Prove or disprove: Between any two vertices in G×H there is either no path at all, or there is a path of length at most m+n.

# 2. Transitive closure

Define the strict transitive closure of a directed graph G to be the relation {(u,v): there is a path of at least one edge from u to v in G}. Prove that the strict transitive closure of a directed graph G is a strict partial order (i.e. an irreflexive transitive relation) if and only if G is acyclic.

# 3. Cut vertices

A cut vertex1 of a graph G is a vertex v whose removal disconnects the graph, i.e. leaves a graph G-{v} with at least two connected components. Prove that every nonempty connected graph has at least one vertex that is not a cut vertex.

# 4. How many cycles?

Show that any nonempty graph G = (V,E) contains at least |E| - |V| + 1 distinct simple cycles.

# 5. Random graphs

A graph on n vertices is constructed by flipping an independent coin for each pair of vertices and including an edge between them if the coin comes up heads, which occurs with probability p.

1. What is the probability that the resulting graph is a complete graph?
2. What is the probability that the resulting graph is a path? (Hint: How many different possible paths are there?)
3. What is the probability that the resulting graph is a cycle?
1. Also called an articulation vertex or articulation point. (1)

2014-06-17 11:57