Activity Sheet 3

Reporter
:
Speaker
:

Section 2.1

  1. What is the degree of each vertex in the \(n\)-cube? Explain using the bit-strings interpretation of the \(n\)-cube.
  2. Exercise 2.12: If \(\Delta(G) + \delta(G) \geq n-1\), then \(G\) is connected and with diameter at most \(4\). Also show by example that \(n-1\) is a sharp bound.
  3. Exercise 2.18: If \(G\) is a graph of order \(8\), and the degrees of the first \(7\) vertices are \(1\), \(2\), \(3\), …, \(7\) respectively, then find the degree of the last vertex. Hint: Try to generalize this to other orders, try some examples with small \(n\).
  4. Exercise 2.14: A graph has the property that every edge joins an odd vertex to an even vertex. Show that the graph is bipartite and has even size.

Section 2.2

  1. For each of the following types of graphs determine if they are always regular graphs, are never regular graphs, or are regular under some further condition (specify).
    1. path graphs
    2. cycle graphs
    3. complete graphs
    4. bipartite graphs