Ryerson Crest Ryerson Header

MTH 607 Graph Theory Lab 1

Work on these questions before the Lab, the TA will take them up.

  1. Consider the graph Qn whose vertices are labeled by strings of length n over {0, 1} (binary strings of length n, eg when n = 3, 000, 001, 010 etc.) There is an edge between to vertices if the strings that label them differ in exactly one place. In general Qn is known as the n-cube.

    So, for example, there is an edge between 000 and 010 which only differ in the second position, but not between 000 and 110 which differ in two places, nor between 000 and 111.

    1. Draw Q3.
    2. Is Q3 bipartite? If so give a bipartition.
    3. In general, for what values of n is Qn bipartite?
    4. Q3 is known as the cubic graph - can you think why?

  2. Generalizing from the previous question define the graph Q(n, t) to be one whose vertices are labeled by strings of length n over {0, 1} (binary strings of length n, eg when n = 3, 000, 001, 010 etc.) There is an edge between to vertices if the strings that label them differ in exactly t places.
    1. Draw Q(2, 2) and give its adjacency matrix.
    2. Draw Q(3, 3).
    3. Give a characterization of Q(n, n) for any n. Justify your characterization.

  3. For each of the following determine conditions on n such that the given graph is bipartite.
    1. Pn.
    2. Cn.
    3. Kn.
    4. K3, n.

  4. For each of the following graphs indicate whether the are subgraphs of K3,3 or subgraphs of the complement of K3,3, or neither. In each case justify your answer.
    1. P5.
    2. C5.
    3. K5.
    4. K2,3.

  5. Given a graph G = (V, E) where V = { a, b, c }, E = { {a, b}, {a, c}, {a, a} }.
    1. Draw G.
    2. Find d(a), d(b) and d(c) and the total degree of G.
    3. Find a walk from a to c which is not a path.
    4. What is the longest simple path in G? (This is called the diameter of a graph.)
    5. Find all non-empty connected subgraphs of G.
      In each case:
      1. If the subgraph is an induced one, indicate the vertices which induce it.
      2. If the subgraph is simple indicate this.

  6. (Hard) Use an acquaintance graph to show that at any party with at least 6 people there are either 3 mutual strangers or 3 mutual acquaintances.

Maintained by: P. Danziger, January 2007