Graph Theory Practice Questions

Let $G$ be a simple connected undirected graph with $n > 2$ vertices.
For any vertex $v$ in $G$, its degree, $deg(v)$, must satisfy $1 \le deg(v) \le n-1$.
This is because:

1. Since the graph is connected and $n>1$, no vertex can have a degree of 0 (it would be isolated). So, $deg(v) \ge 1$.
2. Since the graph is simple, any vertex can be connected to at most $n-1$ other vertices. So, $deg(v) \le n-1$.

Thus, the possible distinct degree values for the $n$ vertices are integers in the set $\{1, 2, \dots, n-1\}$.
The number of distinct possible degree values is $n-1$.
We have $n$ vertices. By the Pigeonhole Principle, if we assign a degree from the set $\{1, 2, \dots, n-1\}$ to each of the $n$ vertices, since there are $n$ vertices (pigeons) and only $n-1$ possible distinct degree values (pigeonholes), at least two vertices must have the same degree.

A graph that does not contain any odd-length cycle is defined as a bipartite graph.
The chromatic number $\chi(G)$ of a graph $G$ is the minimum number of colors needed to color its vertices such that no two adjacent vertices share the same color.
For any connected bipartite graph with at least two vertices ($n \geq 2$), it must contain at least one edge. Thus, one color is insufficient.
Since it is bipartite, its vertices can be partitioned into two sets, $V_1$ and $V_2$, such that all edges connect a vertex in $V_1$ to a vertex in $V_2$. We can color all vertices in $V_1$ with color 1 and all vertices in $V_2$ with color 2.
Therefore, exactly 2 colors are needed.

A connected graph has an Eulerian circuit if and only if every vertex has an even degree.

1. A. Any k-regular graph where k is an even number. This is not necessarily true because the graph might not be connected (e.g., two disjoint $K_3$ graphs, each 2-regular).
2. B. A complete graph on 90 vertices ($K_{90}$). In $K_{90}$, every vertex has degree $90-1=89$. Since 89 is odd, $K_{90}$ does not have an Eulerian circuit.
3. C. The complement of a cycle on 25 vertices ($\bar{C}_{25}$).
   • A cycle graph $C_{25}$ has 25 vertices, and each vertex has degree 2.
   • The degree of a vertex $v$ in its complement $\bar{C}_{25}$ is $(25-1) - \text{deg}_{C_{25}}(v) = 24 - 2 = 22$.
   • Since 22 is an even number, all vertices in $\bar{C}_{25}$ have an even degree.
   • For $n \ge 4$, the complement of a cycle graph $\bar{C}_n$ is connected. Since $n=25$, $\bar{C}_{25}$ is connected.
   • Thus, $\bar{C}_{25}$ is connected and all its vertices have even degrees, so it has an Eulerian circuit.

A topological ordering requires that for every directed edge $u \to v$, vertex $u$ must appear before vertex $v$ in the sequence.

The given DAG has edges including $1 \to 2$ and $1 \to 3$.

1. Option A: $1\ 2\ 3\ 4\ 5\ 6$ - All edges are satisfied.
2. Option B: $1\ 3\ 2\ 4\ 5\ 6$ - All edges are satisfied.
3. Option C: $1\ 3\ 2\ 4\ 6\ 5$ - All edges are satisfied.
4. Option D: $3\ 2\ 4\ 1\ 6\ 5$ - This is not a topological ordering. The edge $1 \to 2$ exists in the DAG, but $1$ appears after $2$ in this sequence ($3\ \underline{2}\ 4\ \underline{1}\ 6\ 5$). Similarly, the edge $1 \to 3$ exists, but $1$ appears after $3$.

violates the definition of a topological ordering.