Here are the /Solutions.

1. Graph products

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

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 vertex¹ 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?