Need help with number 9-12.

1. 9. Let n be a positive integer, and let Sn stand for the directed graph with one vertex for each integer from 0 to n inclusive, and one edge directed from k to l for each pair of integerskandlsuchthat0k
2. 10. A multigraph is a graph in which multiple edges are allowed between vertices. A directed multigraph is a multigraph in which each edge e is assigned a direction, or equivalently, an initial vertex i(e) and a terminal vertex t(e). A cycle in a directed multigraph is a sequence of edges e1,e2,...,en such that t(ek) = i(ek+1) for 1 k < n, and t(en) = i(e1). Informally, this means that a cycle begins and ends at the same vertex. A directed multigraph without cycles is called acyclic. a) Add directions to the edges of a cube to create an acyclic directed graph. Do this in as many essentially distinct ways as you can (i.e., find as many isomorphism classes as you can).

b) Given a multigraph, is it always possible to add directions to its edges to obtain an acyclic directed multigraph? Explain. (Remark: note that multigraphs include graphs as a special case; multiple edges are allowed but not required.)

1. 11. The line digraph or directed edge space or relation space of a directed multigraph G is the graph with one vertex for every edge of G and one edge for every pair of edges e1 and e2 of G such that t(e1) = i(e2). Draw the line digraphs of the simplices in problem 9.
2. 12. Recall the graph dynamics problem we did in class, in which we started with a number of vertices and added edges randomly. Suppose we start with just 5 vertices. What is the probability that the graph will be connected after 3 edges are added? If you cant tell the probability exactly, give a reasonable guess and explanation. Repeat the problem with 4 edges, 5 edges, 10 edges, and 20 edges (if reasonable; go as far as you can reasonably go!) (Remark: to simplify the problem, lets allow the addition of multiple edges between two given vertices if the same pair comes up more than once. This means you dont have to worry about whether an edge is really added each time.)