# 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.

## 1.1. Solution

Proof: Let (u,v) and (u',v') be vertices of G◻H. Then there is a path uu

_{1}u_{2}...u_{k-1}u' of length k ≤ m in G and a path vv_{1}v_{2}...v_{l-1}v' of length l ≤ n in H. Construct a path (u,v)(u_{1},v)(u_{2},v)...(u',v)(u',v_{1})(u',v_{2})...(u',v') in G◻H; this has length k+l ≤ m+n.- Here we have to allow for the possibility that there is no path, because in general G×H need not be connected. However, it is still possible to construct paths of length longer than m+n. For example, let G be a path of length 1 with vertices 0 and 1 and let H be a path of length n (n even) with vertices 0...n, augmented with an extra edge from n-2 to n. There is a length 2n-2 path from 0,0 to 0,1: 0,0 1,1 0,2 1,3 0,4 1,4 ... 0,n-2 1,n-1 0,n 1,n-2 0,n-3 ... 1,2 0,1. But there is no shorter path, because without going out to the loop at the end of H there is no way to make the G-vertex even and the H-vertex odd.

# 2. Transitive closure

Define the **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 transitive closure of a directed graph G is a partial order (i.e. an irreflexive transitive relation) if and only if G is acyclic.

## 2.1. Solution

Write ⇒ for the transitive closure of G.

(If part). We need to show that ⇒ is irreflexive and transitive. Transitivity is easy: if there is a path u⇒v and a path v⇒w, the concatenation of these paths gives a path u⇒w. For irreflexivity, suppose that there is a path of at least one edge from u⇒u; this path is a cycle, and G is not acyclic.

(Only if part). Let G contain a cycle; then for any u on the cycle we have u⇒u, and ⇒ is not irreflexive and thus not a partial order.

# 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.

## 3.1. Solution

Let T be a spanning tree of G, and let v be any leaf of T. Then there is a path in T between any two nodes that are not v. Since every such path is also in G, removing v does not disconnect G.

# 4. How many cycles?

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

## 4.1. Solution

We'll prove it first for connected graphs and then generalize to graphs with more than one connected component. If G is connected, let T be a spanning tree of G. For each edge uv not in T, construct a cycle consisting of uv and the path from v to u in T. Each cycle constructed in this way is distinct since it contains at least one edge that is in none of the others. There are |E| - (|V| - 1) = |E| - |V| + 1 such edges.

If G contains more than one connected component, then each component C contributes at least |E_{C}| - |V_{C}| + 1 cycles; summing up over all components gives ∑_{C} (|E_{C}| - |V_{C}| + 1) ≥ ∑_{C} |E_{C}| - ∑_{C} |V,,C| + 1 = |E| - |V| + 1.

# 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?

## 5.1. Solution

There are (n choose 2) possible edges, and the coin-flips for all of them must come up heads to get a complete graph, so we get a probability of p

^{(n choose 2)}that this event occurs.There are n! ways of ordering the vertices in a path, but because the graph is undirected, any path gives rise to two orderings depending on which end we start from. This gives n!/2 different paths. Each occurs with probability p

^{n-1}(1-p)^{(n choose 2)-n+1}, since the n-1 edges in the path must appear and the remaining edges must*not*appear. Multiplying everything together givestotal probability.

This is similar to the previous case, but we need to find a way to count distinct cycles. One way to write down a cycle is to pick some standard vertex (1, say) and break the cycle just before vertex 1 to make a path. Since 1 is always the first vertex in the path, we get (n-1)! orderings of the remaining vertices. Note however that flipping a cycle over gives a second ordering from the same cycle (undirected graph again), so we have to divide by 2. The probability of getting any particular cycle (with n edges) is p

^{n}(1-p)^{(n choose 2)-n}, so multipling everything together gives

Also called an

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