Graph Theory

One or more correct

• AThe degree of $v$ is at least $k + 1$
• BThe vertex $v$ is on a path of length $k + 1$
• CThe vertex $v$ is on a cycle of length $k + 1$
• DThe vertex $v$ is a part of a clique of size $k$

One or more correct

• AIf $G$ is 2-colorable, then $G$ may contain cycles of odd length
• BIf $G$ is 2-colorable, then $G$ may contain cycles of even length
• CAn optimal algorithm for testing whether $G$ is 2-colorable runs in time $\Theta(|V| + |E|)$, if $G$ is represented as an adjacency list
• DAn optimal algorithm for testing whether $G$ is 2-colorable runs in time $\Theta(|E| \log |V|)$, if $G$ is represented as an adjacency list

Numerical answer

Single correct

• A$\dfrac{1}{n}$
• B$\dfrac{1}{2n-3}$
• C0
• D$\dfrac{1}{n-1}$

Numerical answer

One or more correct

• A$G$ contains a complete subgraph with $k$ vertices
• B$G$ contains an independent set of size at least $n/k$
• C$G$ contains at least $k(k - 1)/2$ edges
• D$G$ contains a vertex of degree at least $k$

Numerical answer

Single correct

• A$G$ is a cycle
• B$G$ is a perfect matching
• C$G$ is a complete graph
• DThere is no such graph $G$

One or more correct

• AAll edges in $G$ have even weight
• BAll edges in $G$ have even weight OR all edges in $G$ have odd weight
• CIn each cycle $C$ in $G$, all edges in $C$ have even weight
• DIn each cycle $C$ in $G$, either all edges in $C$ have even weight OR all edges in $C$ have odd weight

Numerical answer

Numerical answer

Answer key coming soon

One or more correct

• AThis procedure results in a proper vertex coloring of $G$.
• BThe number of colors used is at most $\Delta(G) + 1$.
• CThe number of colors used is at most $\Delta(G)$.
• DThe number of colors used is equal to the chromatic number of $G$.

Answer key coming soon

Numerical answer

Answer key coming soon

Numerical answer

Answer key coming soon

Single correct

• A$A^3$
• B$A^3$ divided by 2
• C$A^3$ divided by 3
• D$A^3$ divided by 6

Answer key coming soon

One or more correct

• AThe chromatic number of the graph is 3.
• BThe graph has a Hamiltonian path.
• CThe graph shown as option (C) in the figure (bottom) is isomorphic to the Peterson graph.
• DThe size of the largest independent set of the given graph is 3. (A subset of vertices of a graph form an independent set if no two vertices of the subset are adjacent.)

Answer key coming soon

One or more correct

• AThe diagonal entries of $A^2$ are the degrees of the vertices of the graph.
• BIf the graph is connected, then none of the entries of $A^{n-1} + I_n$ can be zero.
• CIf the sum of all the elements of $A$ is at most $2(n-1)$, then the graph must be acyclic.
• DIf there is at least a 1 in each of $A$'s rows and columns, then the graph must be connected.

Answer key coming soon

Numerical answer

Answer key coming soon

Numerical answer

Answer key coming soon

Single correct

• A$\text{diam}(G_2) \le \lceil \text{diam}(G)/2 \rceil$
• B$\lceil \text{diam}(G)/2 \rceil < \text{diam}(G_2) < \text{diam}(G)$
• C$\text{diam}(G_2) = \text{diam}(G)$
• D$\text{diam}(G) < \text{diam}(G_2) \le 2\,\text{diam}(G)$

Answer key coming soon