1. (Graph properties)
True or false?
a. The complete bipartite graph K5,5 has no cycle of length five.
b. If you add a new edge to a cycle, the resulting graph will always contain a 3-clique.
c. It is possible to remove two edges from K6 so that the resulting graph has a clique number of 4. d. There are exactly 3 automorphisms of K3.
2. (Graph traversal)
For each of the following graphs, show a Hamiltonian path or argue why no such path exists. a. The graph on slide 18 (week 5).
b. K3,4
c. K1,4,1
d. K2,2,4
e. A graph with 5 nodes and degree sequence 0, 0, 5.
f. A tree with 5 nodes and degree sequence 0, 3, 1, 1.
3. (Graph colouring)
For each of the following graphs G, determine its chromatic number χ(G).
a. The graph on slide 18 (week 5).
b. A graph obtained by adding one new edge to C4.
c. A graph obtained by removing one edge from K2,2.
d. A graph obtained by removing one edge from K4.
4. (Planar graphs)
True or false?
a. A forest is always planar.
b. All graphs with 6 nodes and 8 edges are planar.
c. All graphs whose clique number is 2 are planar.
d. You can obtain a nonplanar graph by adding 3 edges to a cycle.
e. When you remove two edges from K6, you will never obtain a planar graph.
f. All graphs whose chromatic number is 4 are planar.
5. (Constructing graphs)
A graph G is a 2-3 tree if:
G is a rooted tree.
Each node has either 2 or 3 children (unless it is a leaf node, which has no children). All paths from the root to the leaves have the same length.
There are seven different types of 2-3 trees of height 2 (i.e., which are non-isomorphic). Draw one tree of each type.
[hide answer]
6. Challenge Exercise
a. What is the minimum number of edges that need to be removed from K5 so that the resulting graph has a chromatic number of
3 ?
2 ?
1 ?
b. Give a planar drawing of K2,2,2. Can you find one with only straight lines?
