Please provide full solution/explanation

A-6-1. A-6-2. A-6-3. A-6-4. {7 marks} For n > 0, the n-triangle (a.k.a. hypertriangle) is the graph whose vertex set consists of all ternary strings (that is, using digits 0, 1, 2) of length n, and two vertices are adjacent if and only if their strings differ in exactly one position. Justify your answers to each of the following questions. (a) How many vertices and edges does the n-triangle have? (b) Is the n-triangle connected? (c) Does the n-triangle contain an Eulerian circuit? (d) Does the n-triangle contain a bridge? {4 marks} Prove or disprove: Let G = (V, E) be a graph, and let a, b, c V. Suppose that G contains a cycle containing a and b, and a cycle containing b and , and a cycle containing a and . Then G contains a cycle containing a, b, and c. {4 marks} Prove or disprove: Every graph with n vertices has at most n 1 bridges. {5 marks} An equivalent definition of a cut in the graph G is the following: a set of edges Z C E(QG) is a cut if there exists a partition of the vertex set V(G) into disjoint sets V1, V; such that Z is the set of all edges that have one endpoint in V7 and the other endpoint in V5. Let G be a graph, and let a, b, , d be four distinct vertices in G. Suppose further that one cut of G is the set of edges {ab, ac}, and another cut of G is the set of edges {ab, bd}. Prove that {ac,bd} is also a cut of G