Activity Sheet 2

Reporter
:
Speaker
:

Section 1.3

  1. Consider the complete graph in \(5\) vertices. In each of the following explain your reasoning.
    1. Determine how many path subgraphs of this graph there are (these would be identical to \(P_1\), \(P_2\), \(P_3\) or \(P_4\), count separately for each case).
    2. Determine how many cycle subgraphs of this graph there are (\(C_3\) or \(C_4\), count separately for each case).
    3. Determine how many complete proper subgraphs of this graph there are (\(K_1\) through \(K_3\), count separately for each case).
  2. Can the complement of a path/cycle graph be a path/cycle graph? Explain (there are 4 combinations in this question).
  3. Consider a bipartite graph of order \(n\). What is the largest possible value for the size of such a graph? Prove your answer (you may end up using some basic calculus).
  4. Prove that for every \(n\), the \(n\)-th cube is bipartite. You will likely need to do induction on \(n\) to formally prove it, but try to get some intuition by manually trying the cases up to \(n\leq 3\).

Section 1.4

  1. Consider a digraph whose vertices are the courses offered in a department (say mathematics, but your answers below should apply to any department), and where an arc/edge from \(u\) to \(v\) indicates that the course \(v\) has the course \(u\) as a prerequisite.
    1. Must such a digraph be oriented? Explain.
    2. What does it mean to have multiple edges from the same vertex? What does it mean to have multiple edges to the same vertex?
    3. Can such a digraph have a directed cycle in it?
    4. What practical significance does the diameter in such a digraph have?