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.

- Prove or disprove: Between any two vertices in G◻H there is a path of length at most m+n.
- 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**^{1} 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.

- What is the probability that the resulting graph is a complete graph?
- What is the probability that the resulting graph is a path? (Hint: How many different possible paths are there?)
- What is the probability that the resulting graph is a cycle?

Also called an

*articulation vertex*or*articulation point*. (1)