[SOLVED] COMP9020-Set 5 Graphs and Trees

Description

1. (Graph properties)

True or false?

1. The complete bipartite graph K₅,₅ has no cycle of length five.
2. If you add a new edge to a cycle, the resulting graph will always contain a 3-clique.
3. It is possible to remove two edges from K₆ so that the resulting graph has a clique number of 4. d. There are exactly 3 automorphisms of K₃.

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).

1. K₃,4
2. ^K1,4,1
3. ^K2,2,4
4. A graph with 5 nodes and degree sequence 0, 0, 5.
5. 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).

1. The graph on slide 18 (week 5).
2. A graph obtained by adding one new edge to C₄.
3. A graph obtained by removing one edge from K₂,₂.
4. A graph obtained by removing one edge from K₄.

4. (Planar graphs)

True or false?

1. A forest is always planar.
2. All graphs with 6 nodes and 8 edges are planar.
3. All graphs whose clique number is 2 are planar.
4. You can obtain a nonplanar graph by adding 3 edges to a cycle.
5. When you remove two edges from K₆, you will never obtain a planar graph.
6. 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.

6. Challenge Exercise

1. What is the minimum number of edges that need to be removed from K₅ so that the resulting graph has a chromatic number of

3 ?

2 ?

1 ?

2. Give a planar drawing of K₂,2,₂. Can you find one with only straight lines?