Question 3 (5 marks). Prove that for a simple graph G, AG)

Question 3 (5 marks). Prove that for a simple graph G, A(G) S 3 implies that K(G) Hints. We want to prove equality of two quantities, so we need to prove two weak inequalities. We did see in class a relation between K(G), K' (G) and 6(G). You can use it to bound the possible values of K(G). Moreover, it proves immediately one of the two inequalities. The bound on the possible values of allows then to proceed by a case analysis, one case for each possible value, when trying to prove the second inequality. For each case, drawing a schematic example showing a vertex cut of the chosen size will allow you to see easily an edge cut with the required size, proving the inequality. Take care that as K(G) increases, there might be several subcases to consider.