Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

MAST20018 - DiscTete Mathematics and opeTations ReseaTch

Assignment 2

Upload to Canvas bg 5pm Mondag 4th SeptembeT 2023

(a)  State an upper-bound and a lower-bound on the vertex-chromatic number of the graph, and give reasons for your answers.

(b)  Find an optimal colouring of the graph.

(c)  Classify the graph according to the following graph classes: trees, bipartite graphs, interval graphs, chordal graphs. provide a reason for each answer.

(d) Beginning with the matching M  =  {(j, k)},  extend  M  into  a maximum matching by repeatedly inding  augmenting paths.   At each step you should increase the number of edges in the matching by one.  Recall, an augmenting path is an alternating path that joins two “exposed” vertices.

(e)  Find a minimum node-cover for the given graph.   How does the size of the node-cover correspond to the matching you found in the previous question？ why？

(f)  Find an edge-colouring of cardinality four in the graph by repeatedly inding and removing matchings involving all vertices of maximum degree.  All steps must be explicitly shown.

2.  A graph is called a forest if and only if it contains no cycles.  A forest is called a tree if it is connected.  suppose that T is a tree containing n vertices and that F is a forest containing n vertices.

(a)  How many edges does T have？prove your answer.

(b)  If F contains k components (connected pieces) how many edges does F have？prove your answer.

(c)  prove that if we add a single edge e to T then the resulting graph contains exactly one cycle.