Graph Theory Practice Questions

A topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge from vertex $u$ to vertex $v$, $u$ comes before $v$ in the ordering. A graph has a topological ordering if and only if it is a Directed Acyclic Graph (DAG). The given graph is a DAG, so at least one topological ordering exists.

1. Analyze the graph:
   • Edges: $P \to Q$, $P \to R$, $S \to R$, $Q \to Z$, $R \to Z$.
2. Evaluate Option A: Since the graph is a DAG (no cycles), it must have at least one topological ordering. is false.
3. Evaluate Option B (PQRS): In the ordering PQRS, $S$ comes before $R$. However, there is an edge $S \to R$, which means $S$ must come before $R$. This part is consistent. However, consider $P \to R$. In PQRS, $P$ comes before $R$. Consistent.
   Evaluate Option B (SRQP): In the ordering SRQP, $Q$ comes before $P$. But there's an edge $P \to Q$, implying $P$ must come before $Q$. Thus, SRQP is not a valid topological ordering. is false.
4. Evaluate Option C (PSRQ):
   • $P \to Q$: P comes before Q (Consistent)
   • $P \to R$: P comes before R (Consistent)
   • $S \to R$: S comes before R (Consistent)
   • $Q \to Z$: Q comes before Z (Consistent, as Z is not in this sequence)
   • $R \to Z$: R comes before Z (Consistent, as Z is not in this sequence)
   • Thus, PSRQ is a valid topological ordering.
     Evaluate Option C (SPRQ):
   • $P \to Q$: P comes before Q (Consistent)
   • $P \to R$: P comes before R (Consistent)
   • $S \to R$: S comes before R (Consistent)
   • $Q \to Z$: Q comes before Z (Consistent, as Z is not in this sequence)
   • $R \to Z$: R comes before Z (Consistent, as Z is not in this sequence)
   • Thus, SPRQ is also a valid topological ordering.
     is true.
5. Evaluate Option D: Since we found two valid topological orderings in Option C, PSRQ is not the only topological ordering. is false.

A forest is a collection of disjoint trees. Each connected component in a forest is a tree.
For any tree with $V$ vertices, it has exactly $V-1$ edges.
If a forest $G$ has $k$ connected components, let these components be $T_1, T_2, \dots, T_k$.
Let $n_i$ be the number of vertices in component $T_i$, and $e_i$ be the number of edges in $T_i$.
The total number of vertices in the forest is $n = n_1 + n_2 + \dots + n_k$.
The total number of edges in the forest is $e = e_1 + e_2 + \dots + e_k$.
Since each component $T_i$ is a tree, $e_i = n_i - 1$.
Therefore, the total number of edges $e = (n_1 - 1) + (n_2 - 1) + \dots + (n_k - 1) = (n_1 + n_2 + \dots + n_k) - k = n - k$.

Let $G=(V,E)$ be a bipartite graph with $n=12$ vertices. A bipartite graph can be partitioned into two disjoint sets of vertices, say $V_1$ and $V_2$, such that every edge connects a vertex in $V_1$ to one in $V_2$.
To maximize the number of edges, the graph must be a complete bipartite graph, $K_{|V_1|,|V_2|}$. The number of edges in such a graph is $|V_1| \times |V_2|$.
Let $|V_1| = k$. Then $|V_2| = n - k = 12 - k$. The number of edges is $E(k) = k(12-k)$.
To find the maximum value, we can take the derivative of $E(k)$ with respect to $k$ and set it to zero, or recognize that it's a downward-opening parabola. The maximum occurs when $k = 12/2 = 6$.
So, $|V_1| = 6$ and $|V_2| = 12 - 6 = 6$.
The maximum number of edges is $6 \times 6 = 36$.

[CORRECT_OPTION: Not an Option, Numerical Answer]

The total number of vertices in the graph is $12 \times 12 = 144$.
For a vertex $(a,b)$, its neighbors $(c,d)$ must satisfy $|a-c| \le 1$ and $|b-d| \le 1$. This means $c \in \{a-1, a, a+1\}$ and $d \in \{b-1, b, b+1\}$.
If $a, b \in \{2, ..., 11\}$, the vertex has $3 \times 3 - 1 = 8$ neighbors (excluding itself). There are $10 \times 10 = 100$ such vertices.
If $a \in \{1, 12\}$ and $b \in \{2, ..., 11\}$, the vertex has $2 \times 3 - 1 = 5$ neighbors. There are $2 \times 10 \times 2 = 40$ such vertices (2 sides for 'a', 2 sides for 'b' and 10 positions each).
If $a \in \{1, 12\}$ and $b \in \{1, 12\}$, the vertex has $2 \times 2 - 1 = 3$ neighbors. There are $2 \times 2 = 4$ such vertices (corner vertices).
The sum of degrees is $100 \times 8 + 40 \times 5 + 4 \times 3 = 800 + 200 + 12 = 1012$.
By the Handshaking Lemma, the sum of degrees is equal to $2 \times (\text{number of edges})$.
So, the number of edges is $1012 / 2 = 506$.
[CORRECT_OPTION: 506]

A strongly connected component (SCC) is a maximal subgraph where for any two vertices $u, v$ in the subgraph, there is a path from $u$ to $v$ and a path from $v$ to $u$.

Option A creates edges that are not in E, which can change the SCCs.
Option C creates new paths of length $\leq 2$, potentially merging existing SCCs or creating new ones.
Option D removes isolated vertices, which are SCCs of size 1, thus changing the set of SCCs.

Option B defines $G_2$ such that an edge $(u,v)$ exists in $G_2$ if and only if $(v,u)$ exists in $G$. This means $G_2$ is the transpose graph of $G$. If there is a path from $u$ to $v$ in $G$, say $u \to x \to v$, then in $G_2$ there will be a path from $v$ to $u$, $v \to x \to u$. Thus, if $u$ and $v$ are in the same SCC in $G$, they will also be in the same SCC in $G_2$.

A graph $G$ is isomorphic to its complement $\bar{G}$ if there is a bijection $f: V(G) \to V(\bar{G})$ such that $\{u,v\}$ is an edge in $G$ if and only if $\{f(u),f(v)\}$ is an edge in $\bar{G}$.
For a cycle graph $C_n$ with $n$ vertices, the number of edges is $n$.
The complement $\bar{C}_n$ has the same number of vertices $n$. The number of edges in $\bar{C}_n$ is the total possible edges in a complete graph $K_n$ minus the edges in $C_n$.
So, the number of edges in $\bar{C}_n$ is $\frac{n(n-1)}{2} - n$.
For $C_n$ to be isomorphic to $\bar{C}_n$, they must have the same number of edges. Therefore, we set up the equation:
$n = \frac{n(n-1)}{2} - n$
Solving for $n$:
$2n = n(n-1) - 2n$
$4n = n(n-1)$
Since $n$ must be greater than 0 (a cycle requires at least 3 vertices), we can divide by $n$:
$4 = n-1$
$n = 5$
Thus, a cycle on 5 vertices is isomorphic to its complement.

[CORRECT_OPTION: 5]

When Depth First Search (DFS) is performed on a graph represented by an adjacency matrix, visiting each vertex requires checking all $n$ possible edges connected to it. Since there are $n$ vertices in total, and for each vertex, we iterate through its $n$ potential neighbors to find adjacent vertices, the total time complexity becomes $n \times n$. This results in a tight upper bound of $\Theta(n^2)$.

Let's analyze each statement:

(P) The line graph of a cycle $C_n$ ($n \geq 3$) has $n$ vertices (one for each edge of $C_n$). Each vertex in the line graph corresponds to an edge in $C_n$, and these vertices are connected if their corresponding edges are incident in $C_n$. This forms another cycle $C_n$. Hence, statement P is TRUE.

(Q) The line graph of a clique $K_n$ ($n \geq 3$) is not necessarily a clique. For $K_n$, the number of edges is $\frac{n(n-1)}{2}$. The line graph $L(K_n)$ will have $\frac{n(n-1)}{2}$ vertices. If $L(K_n)$ were a clique, then every pair of its vertices would be connected. However, this is not always true for $L(K_n)$. For example, $L(K_3)$ is $K_3$, but $L(K_4)$ is not $K_6$. Hence, statement Q is FALSE.

(R) The line graph of a planar graph is not necessarily planar. For example, the graph $K_4$ is planar, but its line graph $L(K_4)$ is $K_{1,1,1,1}$, which is not planar. Hence, statement R is FALSE.

(S) The line graph of a tree is not necessarily a tree. A tree with $n$ vertices has $n-1$ edges. Its line graph will have $n-1$ vertices. However, the line graph of a tree can contain cycles if the tree has a vertex with a degree greater than 2. For example, a star graph $K_{1,3}$ (a tree) has $3$ edges and its line graph is $K_3$ (a cycle), which is not a tree. Hence, statement S is FALSE.

Based on the analysis, only statement P is TRUE.

To find the expected number of unordered cycles of length three in a graph with 8 vertices, we follow these steps:

First, determine the number of ways to choose 3 vertices out of 8 to form a cycle. This is given by the combination formula:
$\binom{8}{3} = \frac{8!}{3!(8-3)!} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = 56$
For each set of 3 chosen vertices, there is only 1 way to form an unordered cycle of length three (a triangle).

The probability that any specific edge exists is $1/2$. A cycle of length three requires 3 edges to exist between the chosen vertices.
The probability for these 3 specific edges to exist is:
$\left(\frac{1}{2}\right)^3 = \frac{1}{8}$
Finally, the expected number of unordered cycles of length three is the product of the number of possible cycles and the probability that each cycle exists:
$\text{Expected Cycles} = \binom{8}{3} \times \left(\frac{1}{2}\right)^3 = 56 \times \frac{1}{8} = 7$

Let $G=(V,E)$ be an undirected graph, where $V$ is the set of vertices and $E$ is the set of edges. The Handshaking Lemma states that the sum of the degrees of all vertices in an undirected graph is equal to twice the number of edges. That is, $\sum_{v \in V} \text{deg}(v) = 2|E|$.

For statement Q: Since the sum of degrees is always $2|E|$, it must be an even number. Thus, statement Q is TRUE.

For statement P: Let the vertices be divided into two sets: $V_{even}$ for vertices with even degrees and $V_{odd}$ for vertices with odd degrees. We can write the sum of degrees as:
$\sum_{v \in V} \text{deg}(v) = \sum_{v \in V_{even}} \text{deg}(v) + \sum_{v \in V_{odd}} \text{deg}(v)$
Since $\sum_{v \in V} \text{deg}(v)$ is even (from statement Q) and $\sum_{v \in V_{even}} \text{deg}(v)$ is also even (as it's a sum of even numbers), it implies that $\sum_{v \in V_{odd}} \text{deg}(v)$ must be even. The sum of odd numbers is even only if there is an even number of odd numbers. Therefore, the number of odd degree vertices must be even. Thus, statement P is TRUE.

To find the number of distinct cycles of length 4 in a complete undirected graph with 6 labeled vertices, we follow these steps:

1. Choose 4 vertices: A cycle of length 4 requires exactly 4 vertices. From the 6 labeled vertices, we can choose 4 vertices in $\binom{6}{4}$ ways.
2. Arrange the chosen vertices in a cycle: Once 4 vertices are chosen, say $v_1, v_2, v_3, v_4$, they can be arranged to form a cycle. The number of ways to arrange $n$ distinct objects in a cycle is $(n-1)!$. For 4 vertices, this is $(4-1)! = 3!$ ways.
3. Account for duplicate cycles: In an undirected graph, cycles like $v_1-v_2-v_3-v_4-v_1$ and $v_1-v_4-v_3-v_2-v_1$ are considered the same. Also, starting from a different vertex like $v_2-v_3-v_4-v_1-v_2$ results in the same cycle. To correct for this overcounting, we divide by 2 (for the two directions).

Calculating the values:

• Number of ways to choose 4 vertices: $\binom{6}{4} = \frac{6!}{4!(6-4)!} = \frac{6 \times 5}{2 \times 1} = 15$.
• Number of ways to arrange these 4 vertices in a cycle (considering direction): $(4-1)! = 3! = 3 \times 2 \times 1 = 6$.
• Number of distinct cycles of length 4 = $\frac{\binom{6}{4} \times (4-1)!}{2} = \frac{15 \times 6}{2} = \frac{90}{2} = 45$.

Thus, there are 45 distinct cycles of length 4.

To determine which graph is isomorphic to the given graph, we need to compare their structural properties, such as the number of vertices, edges, and degree sequences, and look for specific substructures like cycles.

1. Analyze the given graph:

   • It has 6 vertices.
   • It has 6 edges.
   • The degree sequence is (2, 2, 2, 2, 2, 2), meaning all vertices have a degree of 2.
   • It forms a cycle of length 6.

2. Analyze Option A:

   • It has 6 vertices and 7 edges.
   • The degree sequence is (2, 2, 2, 2, 3, 3).
   • It contains a cycle of length 3 (triangle), which the original graph does not. Thus, not isomorphic.

3. Analyze Option B:

   • It has 6 vertices and 6 edges.
   • The degree sequence is (2, 2, 2, 2, 2, 2).
   • It forms a cycle of length 6.
   • Since it matches all the key properties (number of vertices, edges, degree sequence, and cycle structure) with the given graph, it is isomorphic.

4. Analyze Option C:

   • It has 6 vertices and 6 edges.
   • The degree sequence is (2, 2, 2, 2, 3, 1).
   • It has a vertex of degree 1 and a vertex of degree 3, which the original graph does not. Thus, not isomorphic.

5. Analyze Option D:

   • It has 6 vertices and 6 edges.
   • The degree sequence is (2, 2, 2, 2, 2, 2).
   • It contains a cycle of length 4 (a square), which is different from the cycle of length 6 in the original graph. Thus, not isomorphic.

Based on the comparison, Option B is the only graph that is structurally identical to the given graph.

In a tree data structure, the degree of a node is defined as the number of its direct children. The information that node $A$ has three siblings and a parent $B$ describes $A$'s relationship with other nodes, but it does not specify any children for $A$. Since no children are assigned to $A$, the number of subtrees connected to $A$ is:
$\text{Degree}(A) = 0$
Thus, node $A$ has a degree of 0.

A sequence of numbers can be the degree sequence of a simple graph only if it satisfies certain properties. Let's check the given sequences against two fundamental properties of simple graphs.

Let 'n' be the number of vertices in the graph.

Property 1: Maximum Degree
In a simple graph (no self-loops or multiple edges between the same two vertices), the maximum degree of any vertex cannot exceed $n-1$.

Property 2: Handshaking Lemma
The sum of all degrees in a graph must be an even number, as it is equal to twice the number of edges.

Let's analyze each sequence:

I. 7, 6, 5, 4, 4, 3, 2, 1

• Number of vertices, $n=8$.
• The maximum degree is 7, which is equal to $n-1 = 7$. This is valid.
• The sum of degrees is $7+6+5+4+4+3+2+1 = 32$, which is even. This is valid.
• This sequence is graphical (can be verified with the Havel-Hakimi theorem).

II. 6, 6, 6, 6, 3, 3, 2, 2

• Number of vertices, $n=8$.
• The maximum degree is 6, which is less than $n-1 = 7$. This is valid.
• The sum of degrees is $6+6+6+6+3+3+2+2 = 34$, which is even. This is valid.
• Although it passes the basic checks, applying the Havel-Hakimi algorithm (a recursive test) reveals it is not a graphical sequence. After a few steps, the algorithm results in a sequence with a negative number, which is impossible.

III. 7, 6, 6, 4, 4, 3, 2, 2

• Number of vertices, $n=8$.
• The maximum degree is 7, which is equal to $n-1 = 7$. This is valid.
• The sum of degrees is $7+6+6+4+4+3+2+2 = 34$, which is even. This is valid.
• This sequence is graphical.

IV. 8, 7, 7, 6, 4, 2, 1, 1

• Number of vertices, $n=8$.
• The sequence contains a degree of 8. In a simple graph with 8 vertices, a single vertex can be connected to at most 7 other vertices. Therefore, the maximum possible degree is 7.
• Since $8 > (n-1)$, this sequence violates the maximum degree property and cannot be the degree sequence of a simple graph.

Therefore, sequences II and IV cannot be the degree sequences of any simple graph.

The quantity $\xi(G) = \sum_{d} i_{d} \cdot d$ represents the sum of the degrees of all vertices in a graph G. According to the Handshaking Lemma, the sum of the degrees of all vertices in a graph is equal to twice the number of edges ($2|E|$). Therefore, $\xi(G) = 2|E|$.

For any tree with $|V|$ vertices, the number of edges $|E|$ is always $|V|-1$. Let S and T be two trees with $|S|$ and $|T|$ vertices, respectively.

For tree S, the number of edges is $|S|-1$. Thus, $\xi(S) = 2(|S|-1)$.
For tree T, the number of edges is $|T|-1$. Thus, $\xi(T) = 2(|T|-1)$.

The problem states that $\xi(S) = \xi(T)$.
Therefore, we have the equation: $2(|S|-1) = 2(|T|-1)$.

Dividing both sides by 2, we get:
$|S|-1 = |T|-1$

Adding 1 to both sides gives:
$|S| = |T|$

This shows that if the sum of degrees is the same for two trees, they must have the same number of vertices.