Let G be a simple, finite, undirected graph with vertex set {$$v_1,...,v_n$$}. Let $$\Delta(G)$$ denote the maximum degree of G and let N = {1, 2, ...} denote the set of all possible colors. Color the vertices of G using the following greedy strategy:

for $$i=1,....,n$$

color($$v_i)$$ $$\leftarrow$$ min{$$j\in N$$ : no neighbour of $$v_i$$ is colored $$j$$}

Which of the following statements is/are TRUE?

Let $$U = \{ 1,2,3\} $$. Let 2$$^U$$ denote the powerset of U. Consider an undirected graph G whose vertex set is 2$$^U$$. For any $$A,B \in {2^U},(A,B)$$ is an edge in G if and only if (i) $$A \ne B$$, and (ii) either $$A \supseteq B$$ or $$B \supseteq A$$. For any vertex A in G, the set of all possible orderings in which the vertices of G can be visited in a Breadth First Search (BFS) starting from A is denoted by B(A).

If $$\phi$$ denotes the empty set, then the cardinality of B($$\phi$$) is ___________

Consider a simple undirected unweighted graph with at least three vertices. If A is the adjacency matrix of the graph, then the number of 3-cycles in the graph is given by the trace of

Consider a simple undirected weighted graph G, all of whose edge weights are distinct. Which of the following statements about the minimum spanning trees of G is/are TRUE?