91Ó°ÊÓ

A sports conference has 11 teams. It was proposed that each team play precisely one game against each of exactly nine other conference teams. Prove that this proposal is impossible to implement.

Give an example of a connected graph such that the removal of any edge results in a graph that is not connected. (Assume that removing an edge does not remove any vertices.)

Draw a precedence graph for each computer program. \(x=1\) \(y=2\) \(z=3\) \(a=x+y\) \(b=y+z\) \(c=x+z\) \(c=c+1\) \(x=a+b+c\)

Draw a precedence graph for each computer program. \(x=1\) \(y=2\) \(z=y+2\) \(w=x+5\) \(x=z+w\)

Give an example of a graph with six vertices that has exactly two articulation points.

Show that there is a de Bruijn sequence for every \(n=1,2, \ldots\)

How many paths of length \(k \geq 1\) are there in \(K_{n} ?\)

Let \(G\) be a graph. Define a relation \(R\) on the set \(V\) of vertices of \(G\) as \(v R w\) if there is a path from \(v\) to \(w\). Prove that \(R\) is an equivalence relation on \(V\).

Find the diameter of \(K_{n},\) the complete graph on \(n\) vertices.

Show that the maximum number of edges in an \(n\) -vertex dag is \(n(n-1) / 2\)