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.

1.1. Solution

1. Proof: Let (u,v) and (u',v') be vertices of G◻H. Then there is a path uu₁u₂...u_k-1u' of length k ≤ m in G and a path vv₁v₂...v_l-1v' of length l ≤ n in H. Construct a path (u,v)(u₁,v)(u₂,v)...(u',v)(u',v₁)(u',v₂)...(u',v') in G◻H; this has length k+l ≤ m+n.

2. 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¹ 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.

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?

5.1. Solution

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

2. 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 gives

   total probability.

3. 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ⁿ(1-p)^{(n choose 2)-n}, so multipling everything together gives