Graph theory Statements

All possible statements

The greedy colouring algorithm always produces a valid colouring of a graph G.

TRUE : Explanation: By its very nature, the algorithm assigns a color to each vertex that is different from its already-colored neighbors. This ensures the coloring is valid. It does not, however, guarantee that the coloring is optimal (using the minimum number of colors).

The greedy colouring algorithm computes a colouring of a graph G in polynomial time.

TRUE : Explanation: The algorithm iterates through the vertices once. For each vertex, it checks the colors of its neighbors (at most Δ(G) of them). This is an efficient process that runs in polynomial time.

For any connected graph G on n vertices, it has at least n-1 edges.

TRUE: Explanation: A graph with n vertices and fewer than n-1 edges cannot be connected. A spanning tree is the minimally connected subgraph and has exactly n-1 edges.

If a graph G contains a Hamiltonian cycle (a cycle that includes every vertex), then all vertices in G must have a degree of at least 2.

Answer: TRUE
Explanation: For a vertex to be part of a cycle, it must be connected to two other vertices within that cycle. Therefore, its degree must be at least 2.

If a graph G contains a cycle that includes every vertex, then G must be connected.

Answer: TRUE
Explanation: A Hamiltonian cycle provides a path between any two vertices in the graph, which is the definition of a connected graph.

If a graph G has a Hamiltonian cycle, the number of vertices in G must be even.

Answer: FALSE
Explanation: A triangle (C₃) is a Hamiltonian cycle on 3 vertices, which is an odd number.

A graph is a tree if and only if there is a unique path between any two of its vertices.

Answer: TRUE
Explanation: This is a fundamental definition of a tree. The absence of cycles guarantees that any path between two vertices is unique.

Every tree with n ≥ 2 vertices has at least two leaves (vertices of degree 1).

Answer: TRUE
Explanation: This is a classic theorem about trees, provable using the Handshake Lemma and the fact that |E| = n-1 in a tree.

Adding any new edge between two existing vertices in a tree creates exactly one cycle.

Answer: TRUE
Explanation: Before adding the edge {u, v}, there was already a unique path between u and v in the tree. Adding the edge {u, v} directly connects them, completing this path into a cycle.

Let G be a connected graph and v be a cut vertex (a vertex whose removal disconnects G). If G has a spanning tree T, then v cannot be a leaf in T.

Answer: TRUE
Explanation: If v were a leaf in a spanning tree T, its removal would only disconnect itself, not the rest of the tree. Since T connects the graph, removing a leaf from T would not disconnect G. Therefore, a cut vertex must be an internal node of any spanning tree.

A graph is bipartite if and only if it is 2-colorable.

Answer: TRUE
Explanation: This is the definition of a bipartite graph. The two sets of the partition (e.g., A and B) can each be assigned one of the two colors.

A graph is bipartite if and only if it contains no odd-length cycles.

Answer: TRUE
Explanation: This is the key structural characterization of bipartite graphs. An odd cycle forces at least one edge to connect two vertices of the same color in any 2-coloring attempt.

If a graph G is bipartite, the greedy colouring algorithm is guaranteed to colour it with at most 2 colours.

Answer: FALSE
Explanation: This is a classic trick question. The graph is 2-colorable, but a poor ordering of vertices can force the greedy algorithm to use more than 2 colors.

For a bipartite graph G on n vertices, the size of the largest stable set (α(G)) is at least n/2.

Answer: TRUE
Explanation: A bipartite graph can be partitioned into two independent sets, A and B, where |A| + |B| = n. The larger of these two sets must have a size of at least n/2.

Every bipartite graph is 3-colorable.

Answer: TRUE
Explanation: Since every bipartite graph is 2-colorable (χ(G) ≤ 2), it is by definition also 3-colorable (χ(G) ≤ 3).

For a simple, connected planar graph with |V| ≥ 3, it is always true that |E| ≤ 3|V| - 6.

Answer: TRUE
Explanation: This is a famous upper bound on the number of edges in a planar graph, derived from Euler's Formula. It's often used to quickly prove a graph is non-planar.

Every simple, connected planar graph has at least one vertex with a degree of 5 or less.

Answer: TRUE
Explanation: This is a direct consequence of the formula |E| ≤ 3|V| - 6 and the Handshake Lemma. If every vertex had a degree of 6 or more, the number of edges would exceed this bound.

Every planar graph is 5-colorable.

Answer: TRUE
Explanation: This is the Five Color Theorem.

Let G be a planar, connected graph with at least 4 vertices. G has at most 3|V| - 7 edges.

Answer: FALSE
Explanation: The correct tight bound is 3|V| - 6. The statement is not always true (e.g., a maximal planar graph has exactly 3|V| - 6 edges).

The Max-Flow Min-Cut Theorem states that the value of a maximum flow is equal to the capacity of a minimum cut.

Answer: TRUE
Explanation: This is the central theorem of network flow theory, connecting the concepts of flow and cuts.

A flow f is maximum if and only if there is no augmenting path in its residual network N_f.

Answer: TRUE
Explanation: This is the Augmenting Path Theorem. The existence of an s-t path in the residual network implies that the flow can be increased.

If no s-t path exists in the residual network N_f, then f is a maximum flow.

Answer: TRUE
Explanation: This is another way of stating the Augmenting Path Theorem, forming the termination condition for the Ford-Fulkerson algorithm.

In any bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover (ν(G) = τ(G)).

Answer: TRUE
Explanation: This is König's Theorem.

A matching M is maximum if and only if there is no M-augmenting path in the graph.

Answer: TRUE
Explanation: This is Berge's Lemma, the fundamental principle for finding maximum matchings.

The symmetric difference of two matchings, M and M', consists of only paths and even cycles.

Answer: TRUE
Explanation: In the graph formed by the edges M Δ M', every vertex has a degree of at most 2. Any graph with maximum degree 2 is a collection of disjoint paths and cycles. The cycles must be even because their edges must alternate between M and M'.

If M and M' are two matchings in a graph G with |M| < |M'|, then there must exist an M-augmenting path.

Answer: TRUE
Explanation: A consequence of Berge's Lemma. Since |M'| > |M|, the symmetric difference M Δ M' must contain at least one path that has more edges from M' than from M, which will be an M-augmenting path.

The TSP-Backtrack algorithm is guaranteed to find an optimal solution to the Traveling Salesperson Problem.

Answer: TRUE
Explanation: Backtracking is a form of exhaustive search. By exploring all possible valid tours, it is guaranteed to find the optimal one, though it may take exponential time.

The Nearest-Neighbour algorithm finds a feasible solution to the TSP in polynomial time.

Answer: TRUE
Explanation: Nearest-Neighbour is a greedy heuristic. It is fast and always produces a valid tour (a feasible solution), but this tour is often not the optimal one.

The Nearest-Neighbour algorithm finds an optimal solution to the TSP.

Answer: FALSE
Explanation: It is a heuristic, not an exact algorithm. It frequently produces suboptimal tours.

The fractional knapsack problem can be solved optimally in polynomial time.

Answer: TRUE
Explanation: A simple greedy algorithm (sorting by value-to-weight ratio) solves the fractional knapsack problem optimally and efficiently.

A polynomial-time reduction f from problem A to problem B (A ≤p B) must be computable in polynomial time.

Answer: TRUE
Explanation: This is part of the definition of a polynomial-time reduction. The transformation f itself must be efficient.

A reduction f from problem A to B (A ≤p B) must convert every yes-instance of A into a yes-instance of B.

Answer: TRUE
Explanation: This is the core property of a reduction. It maps solvable instances to solvable instances, preserving the answer. (x ∈ A <=> f(x) ∈ B).

If a primal LP has an optimal solution, and its corresponding dual LP has an optimal solution, their objective function values are equal.

Answer: TRUE
Explanation: This is the Strong Duality Theorem.

If a primal LP is unbounded, then its dual LP must be infeasible.

Answer: TRUE
Explanation: This is a key part of the Weak Duality Theorem's consequences.

If a primal LP has a feasible solution, then its dual LP must also have a feasible solution.

Answer: FALSE
Explanation: The primal could be feasible but unbounded. In this case, the dual problem is infeasible.

If both the primal and the dual LP have feasible solutions, then both must have optimal solutions.

Answer: TRUE
Explanation: If both are feasible, the Weak Duality theorem implies that neither can be unbounded. A feasible, bounded LP must have an optimal solution.