AGT Quiz FlashCard

Graph_Theory_Basics QUESTION: Is a connected K-regular graph always a vertex-transitive graph? OPTIONS: A) True B) False ?? SOLUTION: A connected K-regular graph is not always vertex-transitive. Vertex transitivity requires that for any two vertices u and v, there exists an automorphism that maps u to v. While K-regular graphs have a uniform degree, this doesn’t guarantee the existence of such automorphisms for all vertex pairs. A counterexample can be constructed. Therefore, the statement is False.

Cut_Vertices QUESTION: In the given graph, identify the cut vertices. OPTIONS: A) B and E B) C and D C) A and E D) C and B ?? SOLUTION: A cut vertex is a vertex whose removal (along with its incident edges) increases the number of connected components in the graph.

• Removing B disconnects A and D from the rest of the graph.
• Removing E disconnects D. Therefore, B and E are cut vertices.

Bipartite_Graphs QUESTION: There are four students A, B, C, and D. A says a triangle is a bipartite graph. B says a pentagon is a bipartite graph. C says a square is a bipartite graph. D says a heptagon is a bipartite graph. Who is correct? OPTIONS: A) A B) B C) C D) D ?? SOLUTION: A bipartite graph is a graph whose vertices can be divided into two disjoint sets such that every edge connects a vertex in one set to a vertex in the other set. Equivalently, a graph is bipartite if and only if it contains no odd-length cycles.

• A triangle (3-cycle) is not bipartite (odd cycle).
• A pentagon (5-cycle) is not bipartite (odd cycle).
• A square (4-cycle) is bipartite.
• A heptagon (7-cycle) is not bipartite (odd cycle). Therefore, only C is correct.

Breadth_First_Search QUESTION: Consider an undirected unweighted graph G. Let a breadth-first traversal of G be done starting from a node r. Let $d(r,u)$ and $d(r,v)$ be the lengths of the shortest paths from r to u and v respectively in G. If u is visited before v during the breadth-first traversal, which of the following statements is correct? OPTIONS: A) $d(r,u)<d(r,v)$ B) $d(r,u)>d(r,v)$ C) $d(r,u)\le d(r,v)$ D) None of the above ?? SOLUTION: In a breadth-first search (BFS), vertices are visited in increasing order of their distance from the starting node. If u is visited before v, it means that the shortest path from r to u is either shorter than or equal to the shortest path from r to v. Therefore, $d(r,u)\le d(r,v)$.

Graph_Union_Intersection QUESTION: Let $G_1=(V,E_1)$ and $G_2=(V,E_2)$ be connected graphs on the same vertex set V with more than two vertices. If $G_1\cap G_2=(V,E_1\cap E_2)$ is not a connected graph, then the graph $G_1\cup G_2=(V,E_1\cup E_2)$ OPTIONS: A) Can’t have a cut vertex B) Must have a cycle C) Must have a cut edge (bridge) D) Has a chromatic number strictly greater than those of $G_1$ and $G_2$ ?? SOLUTION: If the intersection of two connected graphs is disconnected, their union must have a cycle. Consider a simple example: $G_1$ is a path a-b-c, and $G_2$ is a path a-c-b. Their intersection is the disconnected set {a, b, c}, while their union is a cycle a-b-c-a. The union must have a cycle.

Planar_Graphs QUESTION: A Peterson graph is non-planar because: OPTIONS: A) It’s a subgraph that contains a subdivision of $K_5$ B) It’s a subgraph that contains a subdivision of $K_{3,3}$ C) It contains a $K_5$ minor D) Both B and C ?? SOLUTION: Kuratowski’s theorem states that a graph is planar if and only if it does not contain a subgraph that is a subdivision of $K_5$ (the complete graph on 5 vertices) or $K_{3,3}$ (the complete bipartite graph on two sets of 3 vertices). The Peterson graph contains subdivisions of both and also K5 Minor. So Both B and C are correct.

Cycle_Decomposition QUESTION: Cycle decomposition is possible in a graph G if: OPTIONS: A) G is a regular graph B) G is a complete graph C) G is an Euler graph D) None of these ?? SOLUTION: A graph has a cycle decomposition if and only if all its vertices have even degree. This is the definition of an Eulerian graph. A regular graph may have a cycle decomposition (if the degree is even), but it’s not guaranteed. A complete graph with an odd number of vertices does not have a cycle decomposition.

Chromatic_Number QUESTION: What will be the chromatic number for an empty graph having N vertices? OPTIONS: A) 0 B) 1 C) 2 D) N ?? SOLUTION: An empty graph has no edges. Therefore, each vertex can be assigned the same color (e.g., color 1) without violating the coloring rule (adjacent vertices must have different colors). The chromatic number is 1.

Radius_Diameter QUESTION: Which relation given below is true? OPTIONS: A) $rad(G)\le diam(G)\le 2\ast rad(G)$ B) $rad(G)\le diam(G)\ge 2\ast rad(G)$ C) $rad(G)<diam(G)<2\ast rad(G)$ D) All of the above ?? SOLUTION: The radius of a graph is the minimum eccentricity of any vertex, and the diameter is the maximum eccentricity. The eccentricity of a vertex is the greatest distance between that vertex and any other vertex. The correct relationship is: $rad(G)\le diam(G)\le 2\ast rad(G)$.

Vertex_Cover_Independent_Set QUESTION: Let G be a simple graph with 20 vertices and 100 edges. The size of the minimum vertex cover of G is 8. Then, the size of the maximum independent set of G is: OPTIONS: A) 12 B) 8 C) Less than 8 D) More than 12 ?? SOLUTION: For any graph, the sum of the size of a minimum vertex cover and the size of a maximum independent set is equal to the number of vertices. Therefore, if the minimum vertex cover has size 8, and there are 20 vertices, the maximum independent set has size 20 - 8 = 12.

Degree_and_Vertices QUESTION: A graph has 24 edges and the degree of each vertex is k, then which of the following is a possible number of vertices? OPTIONS: A) 20 B) 15 C) 10 D) 8 ?? SOLUTION: By the Handshaking Lemma, the sum of the degrees of all vertices in a graph is equal to twice the number of edges. Let n be the number of vertices. Then, n * k = 2 * 24 = 48. We need to find a factor of 48 among the options.

• 48 / 8 = 6. 8 is a possible.

Complement_of_Disconnected_graph QUESTION: If G is a disconnected graph, then its complement, denoted as $C(G)$ or $\bar{G}$, has which property? OPTIONS: A) $C(G)$ is disconnected B) $C(G)$ is connected and $diam(G)\le 1$ C) $C(G)$ is connected and $diam(\bar{G})\le 2$ D) None of these ?? SOLUTION: If G is disconnected it has at least two components. In the complement $\bar{G}$, every vertex in one component of G is adjacent to every vertex in all other components of G. Consider two vertices $u$ and $v$. Case 1: If $u$ and $v$ are in different components of G. They aren’t adjacent in G. Thus they are adjacent in $\bar{G}$. Therefore, $d(u,v)=1$ Case 2: If $u$ and $v$ are in the same component in G. Because there’s at least two components, there must exist a third vertex $w$ in a component that is not the same as $u$‘s and $v$‘s. Then in $\bar{G}$: $u$ is not adjacent to $v$, BUT $u$ is adjacent to $w$ and $v$ is adjacent to $w$. That means, that there exist a path $u-w-v$ of length 2 between $u$ and $v$. The distance between $u$ and $v$ is $d(u,v)=2$ Since, the maximum distance is 2, the $diam(\bar{G})\le 2$. Therefore the answer is C.

Wagners_Theorem QUESTION: Wagner’s theorem states that a graph is planar if and only if it has no $K_5$ or $K_{3,3}$ minor. OPTIONS: A) True B) False ?? SOLUTION: Wagner’s theorem is equivalent to Kuratowski’s theorem. It’s a correct statement concerning planarity. Therefore the answer is True

Computational_Complexity QUESTION: Calculating the chromatic number of a graph is a OPTIONS: A) P problem B) NP-hard problem C) NP-complete problem D) Cannot be identified as any of the given problems ?? SOLUTION: Finding the chromatic number of a graph is a classic NP-complete problem. There is no known polynomial-time algorithm to solve it, and it’s verifiable in polynomial time.

Computational_Complexity_2 QUESTION: Finding the minimum connected dominating set is: OPTIONS: A) NP Problem B) P Problem C) NPC Problem D) None of These ?? SOLUTION: The minimum connected dominating set problem is NP-Complete

Non_Trivial_Graph_Cut_Vertices QUESTION: Every non-trivial connected graph contains $\ge$ 2 vertices that are not cut vertices. OPTIONS: A) True B) False ?? SOLUTION: This statement is true. Consider a spanning tree of the connected graph. The leaves of the spanning tree are not cut vertices (removing a leaf does not disconnect the tree). A non-trivial connected graph (one with at least two vertices) must have at least two leaves in any spanning tree.

Independent_set_and_vertex_cover QUESTION: $I$ is an independent set in G, if and only if $V(G)-I$ is a vertex cover of G. OPTIONS: A) V(G) is a vertex cover B) V(G) - I is a vertex cover of G C) Both a and b D) None of these ?? SOLUTION: This is a fundamental relationship between independent sets and vertex covers. If I is an independent set, no two vertices in I are adjacent. Therefore, every edge in the graph must have at least one endpoint outside of I, meaning at least one endpoint in $V(G)-I$. This is the definition of a vertex cover. The reverse also holds.

Chromatic_number_of_given_graph QUESTION: The minimum number of colours required to color the graph is: OPTIONS: A) 2 B) 3 C) 4 D) 5 ?? SOLUTION: By observation. The inner cycle requires 3 colours. The outer vertices are connected to form an almost K4. But because of the structure, we don’t need 4, 3 is sufficient.

spanning_trees QUESTION: Consider a complete graph G with 4 vertices. The graph G has ___ spanning trees. OPTIONS: A) 15 B) 8 C) 16 D) 13 ?? SOLUTION: Cayley’s formula states that for a complete graph with n vertices, the number of spanning trees is $n^{(n-2)}$. For n = 4, this is $4^{(4-2)}=4^2=16$.

Complete_Graph_Spanning_Trees_General QUESTION: The complete graph $K_n$ has… different spanning trees? OPTIONS: A) $n^{(n-2)}$ B) $n^n-2$ C) n/2 D) $n^2-2$ ?? SOLUTION: This is Cayley’s formula: $n^{(n-2)}$.

Cycle_Complement_Isomorphism QUESTION: A cycle on n vertices is isomorphic to its complement. The value of n is ___. OPTIONS: A) 2 B) 4 C) 5 D) 6 ?? SOLUTION: A cycle on n vertices ($C_n$) has n edges. Its complement has $\frac{n(n-1)}{2}-n$ edges. For the graph and its complement to be isomorphic, they must have the same number of edges. So, $n=\frac{n(n-1)}{2}-n$. Simplifying, $2n=\frac{n(n-1)}{2}$, $4n=n(n-1)$, $4=n-1$ (since n cannot be 0), and thus $n=5$.

bridges_in_graph QUESTION: The Number of bridges in the given graph is : OPTIONS: A) 1 B) 2 C) 4 D) 3 ?? SOLUTION: A bridge is an edge whose removal increases the number of connected components. In this graph, the edges (1,2), (3,4) and (6,7) are bridges. So the answer is 3.

Hamiltonian_Path_Circuit QUESTION: If a graph has a Hamiltonian path, then it is possible that the graph also has a Hamiltonian circuit. OPTIONS: A) True B) False ?? SOLUTION: If a graph has a Hamiltonian path, it doesn’t necessarily have a Hamiltonian circuit. However, it is possible. For example a simple path of 3 nodes has a Hamiltonian path but not circuit. However, if we join the end nodes of path of three nodes we can create a cycle which have both Hamiltonian circuit and path. So the Answer should be True.

Maximum_edges_bipartite QUESTION: The maximum number of edges in a bipartite graph on 12 vertices is: OPTIONS: A) 36 B) 48 C) 12 D) 24 ?? SOLUTION: In a bipartite graph with n vertices, the maximum number of edges occurs when the vertices are divided as evenly as possible into the two sets. With 12 vertices, we have two sets of 6 vertices each. The maximum number of edges is then 6 * 6 = 36.

Radius_and_Diameter_2 QUESTION: Which relation is true? OPTIONS: A) $\text{rad}(G)\le \text{diam}(G)\le 2\ast \text{rad}(G)$ B) $\text{rad}(G)\le \text{diam}(G)\ge 2\ast \text{rad}(G)$ C) $\text{rad}(G)<\text{diam}(G)<2\ast \text{rad}(G)$ D) All of the above. ?? SOLUTION: Option A

Planarity_k5_k33 QUESTION: Peterson Graph is Non-Planar because? OPTIONS: A) It’s a subgraph that contains a subdivision of $K_5$. B) It’s a subgraph that contains a subdivision of $K_{3,3}$ C) It contains a $K_5$ minor. D) Both B and C. ?? SOLUTION: Option D

Eulerian_Circuit_Conditions QUESTION: Which of the following graphs has an Eulerian circuit? OPTIONS: A) Any k regular graph where k is an even number. B) A complete graph on 90 vertices. C) Complement of a cycle on 25 vertices. D) None of the above ?? SOLUTION: A graph has an Eulerian circuit if and only if every vertex has an even degree.

• (A) is correct because every vertex has degree k, and k is even.
• (B) A complete graph on 90 vertices ($K_{90}$) has vertices of degree 89 (odd), so it doesn’t have an Eulerian circuit.
• (C) A cycle on 25 Vertices ($C_{25}$) has a degree of 2. The Complement of Cycle on 25 vertices have a degree of (24-2) = 22 which is even.

Connected_components QUESTION: The most efficient algorithm for finding the number of connected components in an undirected graph on n vertices and m edges is come under which class? OPTIONS: A) NP Problem B) P Problem C) NPC problem D) None of these ?? SOLUTION: Finding connected components can be done in linear time, O(m+n), using Depth-First Search (DFS) or Breadth-First Search (BFS). Thus, it is in P.

Spanning_trees_n_vertices_n_edges QUESTION: What is the largest integer m such that every simple connected graph with n vertices and n edges contains at least m different spanning trees? OPTIONS: A) 1 B) 2 C) 3 D) n ?? SOLUTION: A simple connected graph with n vertices and n edges must contain exactly one cycle. If you remove any single edge from the cycle, you create a spanning tree. Since the cycle contains at least 3 edges in a simple graph and, after removing any one edge from a cycle, we have at least one cycle. The graph with n vertices and n edges will have at least n spanning trees if it’s a cycle, But it always has one cycle, therefore, removing one of edge from that cycle will lead to the creation of one spanning tree.

connected_planar_graph QUESTION: A connected planar graph having 6 vertices, 7 edges contains ____ regions. OPTIONS: A) 15 B) 3 C) 1 D) 11 ?? SOLUTION: By Euler’s formula for planar graphs: V - E + R = 2, where V is vertices, E is edges, and R is regions. So, 6 - 7 + R = 2, R = 3.

Distinct_Simple_Graphs QUESTION: The number of distinct simple graphs with up to three nodes is: OPTIONS: A) 15 B) 10 C) 7 D) 9 ?? SOLUTION: We list the possibilities:

• 0 vertices: 1 graph (the empty graph)
• 1 vertex: 1 graph (a single isolated vertex)
• 2 vertices: 2 graphs (either connected by an edge or not)
• 3 vertices:
• No edges: 1
• One edge: 1 (all isomorphic)
• Two edges: 1(all isomorphic)
• Three edges(C3): 1 Total= 1+1+2+4 = 8. But, considering the wording up to, we have already considered one and two nodes graphs in the previous case. The question isn’t worded very well but consider only 3 vertices there are total 4 distinct graphs. The closest answer, given the choices is none of the above

Planar_Graph_K4_Q3 QUESTION: Which statement is true? (Graphs K4 and Q3 shown) OPTIONS: A) K4 is planar while Q3 is not B) Both K4 and Q3 are planar C) Q3 is planar while K4 is not D) Neither K4 nor Q3 is planar ?? SOLUTION: Q3 (the cube) is planar. K4 (the complete graph on 4 vertices) is also planar.

Hamiltonian_Path_Problem QUESTION: Which of the following problems is similar to that of a Hamiltonian path problem? OPTIONS: A) Knapsack Problem B) Closet pair problem C) Assignment Problem D) Traveling Salesman Problem ?? SOLUTION: The Traveling Salesman Problem (TSP) is closely related to the Hamiltonian path problem. TSP seeks the shortest Hamiltonian cycle, while the Hamiltonian path problem seeks a path that visits each vertex exactly once.

Connected_Planar_Regions QUESTION: Let G be a connected planar simple graph with 25 vertices and 60 edges. Find the number of regions in G. OPTIONS: A) 35 B) 37 C) 83 D) 90 ?? SOLUTION: Using Euler’s formula, V - E + R = 2. 25 - 60 + R = 2. R = 37.

Adjacency_Matrix_Principal_Diagonal QUESTION: Let X be the adjacency matrix of a graph G with no self-loops. The entries along the principal diagonal of X are: OPTIONS: A) Different B) All zeroes C) All ones D) Infinity ?? SOLUTION: The adjacency matrix has a ‘1’ at position (i, j) if there’s an edge between vertex i and vertex j, and ‘0’ otherwise. With no self-loops, there are no edges from a vertex to itself, so the diagonal (i, i) entries are all 0.

regular_graph_edges QUESTION:The Number of edges in a regular graph of degree 46 and 8 vertices is ____. OPTIONS: A) 347 B) 230 C) 184 D) 186 ?? SOLUTION: Handshaking lemma: sum of degrees = 2 * number of edges. 8 * 46 = 2 * E. E = 184.

Max_edges_undirected_no_self_loop QUESTION: The maximum number of edges in an n-node undirected graph without self-loops is: OPTIONS: A) N^2 B) N * (N - 1) / 2 C) N - 1 D) (N + 1) * N / 2 ?? SOLUTION: This is a complete graph, and the number of edges is given by the combination formula: nC2 = n*(n-1)/2.

Edges_in_Regular_Graph QUESTION: The number of edges in a regular graph of degree d and n vertices is: OPTIONS: A) n + d B) nd C) nd / 2 D) n * (n - 1) / 2 ?? SOLUTION: By the Handshaking Lemma, the sum of the degrees is equal to twice the number of edges. Since each of the n vertices has degree d, the sum of degrees is nd. Therefore, the number of edges is nd / 2.

Adjacency_List_Matrix_Representation QUESTION: Which of the following statements is/are true? I) Adjacency list representation is better for sparse graphs than the adjacency matrix representation. II) Adding a vertex in adjacency list representation is easier than Adjacency matrix representation III) Finding whether there is an edge between any two nodes in a graph is easier in Adjacency list representation. OPTIONS: A) I only B) I and III only C) I, II and III D) I and II only ?? SOLUTION: I) TRUE: Adjacency lists only store existing edges, saving space for sparse graphs. Adjacency matrices store all possible edges. II) TRUE: Adding a vertex to an adjacency list just requires adding a new list head. A matrix often needs resizing, copying the entire matrix. III) FALSE: Finding an edge in an adjacency matrix is O(1) (direct access). In an adjacency list, it’s O(degree of the vertex) in worst case.

min_edges_non_planar QUESTION: Let $G$ be the non-planar graph with the minimum possible number of edges. Then $G$ has: OPTIONS: A) 9 edges and 5 vertices B) 9 edges and 6 vertices C) 10 edges and 5 vertices D) 10 edges and 6 vertices ?? SOLUTION: The smallest non-planar graphs are $K_5$ (5 vertices, 10 edges) and $K_{3,3}$ (6 vertices, 9 edges). Therefore, the correct answer is B, 9 edges and 6 vertices with $K_{3,3}$

undirected_graphs_count QUESTION: How many undirected graphs (not necessarily connected) can be constructed out of a given set $V=\{v_1,v_2,...v_n\}$ of n vertices? OPTIONS: A) $n(n-1)/2$ B) $2^n$ C) $n!$ D) $2^{n(n-1)/2}$ ?? SOLUTION: For each pair of vertices $(v_i,v_j)$, we have two choices: either include an edge between them or not. There are $n(n-1)/2$ such pairs (combinations of n items taken 2 at a time). So total number of undirected graphs that are possible is $2^{n(n-1)/2}$.

planar_graph_bounded_faces QUESTION: Let $G$ be a simple undirected planar graph on 10 vertices with 15 edges. If $G$ is a connected graph, then the number of bounded faces in any embedding of $G$ on the plane is equal to: OPTIONS: A) 4 B) 5 C) 6 D) 7 ?? SOLUTION: By Euler’s formula for connected planar graphs: $v-e+f=2$, where $v$ is the number of vertices, $e$ is the number of edges, and $f$ is the number of faces (including the unbounded, outer face). Here, $v=10$, $e=15$. $10-15+f=2$ $f=7$ This gives the total number of faces. The unbounded face is always 1. Thus the Number of bounded faces are 7-1 = 6.

statements_about_complexity QUESTION: Which of the following statements are TRUE? a) The problem of determining whether there exists a cycle in an undirected graph is in P. b) The problem of determining whether there exists a cycle in an undirected graph is in NP. c) If a problem A is NP-Complete, there exists a non-deterministic polynomial time algorithm to solve A. OPTIONS: A) a, b, c B) a, c C) b, c D) a, b ?? SOLUTION: (a) is TRUE. Cycle detection can be done in polynomial time using Depth-First Search (DFS). (b) is TRUE. Any problem in P is also in NP. (c) is TRUE. This is the definition of NP-completeness – a problem is in NP, and every other problem in NP can be reduced to it in polynomial time. A non-deterministic Turing Machine can solve all problems within NP in polynomial time.

np_complete_reduction QUESTION:Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial-time reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true? OPTIONS: A) R is NP-complete B) R is NP-hard C) Q is NP-complete D) Q is NP-hard ?? SOLUTION:

• S is NP-complete: This is given.
• Q is polynomial-time reducible to S: This means Q is “no harder than” S. Since S is NP-hard, this makes Q NP-hard as well. However, we don’t know if Q is in NP, so we can’t say it’s NP-complete.
• S is polynomial-time reducible to R: This means R is at least as hard as S. Since S is NP-hard, R must also be NP-hard. We don’t know if R is in NP. Therefore, R is at least as hard as a known NP-Complete problem. Hence, R is NP-Hard.

planarity_of_graphs QUESTION: Which of the following graphs is planar? (Graphs G1, G2, G3, G4 are provided) OPTIONS: A) G1 B) G2 C) G3 D) G4 ?? SOLUTION: G1 is not planar since it is K5, while G2,G3 and G4 are planar graphs.

same_degree_vertices QUESTION: Which one of the following is TRUE for any simple connected undirected graph with more than 2 vertices? OPTIONS: A) No two vertices have the same degree B) At least two vertices have the same degree C) At least three vertices have the same degree D) None of these ?? SOLUTION: In a simple graph with n vertices, the possible degrees range from 0 to n-1. If n > 2, consider two cases. Case 1. If there is a vertex with degree (n-1) , it connected with all other nodes. Therefor, there cannot be a node with degree 0. There are only n-1 options for degree. By pigeon hole principle, we will have at least two vertices that will have the same degree. Case 2: If there isn’t any node with n-1 degree, the degree options are between 0 to n-2, that is also n-1 options for the degree. By pigeon hole principle, at least two vertices must have the same degree.

components_after_vertex_removal QUESTION: Let $G$ be an arbitrary graph with n nodes and k components. If a vertex is removed from $G$, the number of components in the resultant graph must necessarily lie between OPTIONS: A) k and n B) k-1 and k+1 C) k-1 and n-1 D) k+1 and n-k ?? SOLUTION:

• Removing a vertex can at most increase the number of components by the number of edges incident to that vertex, which, in the worst case, can increase the components as much as disconnecting all other remaining n-1 vertex.
• Removing a cut vertex will lead to increment by 1
• Removing a vertex can at least decrease the number of components by 1 (if the removed vertex was an isolated component). It can also keep number of component same, if the removed vertex is not a cut vertex. Therefore the correct range is [k-1, n-1].

expected_number_of_cycles QUESTION: Consider an undirected random graph of eight vertices. The probability that there is an edge between a pair of vertices is 1/2. What is the expected number of unordered cycles of length three? OPTIONS: A) 1/8 B) 1 C) 7 D) 8 ?? SOLUTION: Number of ways to choose 3 vertices from 8 is 8C3 = (8*7*6)/(3*2*1) = 56. The probability of a cycle existing between these 3 chosen vertices = (1/2)*(1/2)*(1/2) = 1/8. Because Probability of forming an edge is 1/2. Expected number of cycles of length 3 = 56 * (1/8) = 7