Question Details

An undirected, unweighted, simple graph G(V,E) is said to be 2-colorable if there exists a function c : V → {0,1} such that for every (u,v) ∈ E,c(u) ̸ = c(v). Which of the following statements about 2-colorable graphs is/are true?

Options

A

If G is 2-colorable, then G may contain cycles of odd length

B

If G is 2-colorable, then G may contain cycles of even length

C

An optimal algorithm for testing whether G is 2-colorable runs in time Θ(|V | + |E|), if G is represented as an adjacency list

D

An optimal algorithm for testing whether G is 2-colorable runs in time Θ(|E|log|V |), if G is represented as an adjacency list

Show Answer
Correct Answer
B If G is 2-colorable, then G may contain cycles of even length
C An optimal algorithm for testing whether G is 2-colorable runs in time Θ(|V | + |E|), if G is represented as an adjacency list
B If G is 2-colorable, then G may contain cycles of even length
C An optimal algorithm for testing whether G is 2-colorable runs in time Θ(|V | + |E|), if G is represented as an adjacency list
A If G is 2-colorable, then G may contain cycles of odd length
B If G is 2-colorable, then G may contain cycles of even length
C An optimal algorithm for testing whether G is 2-colorable runs in time Θ(|V | + |E|), if G is represented as an adjacency list

Solution :

The correct statements about 2-colorable graphs are:
1. If G is 2-colorable, then G may contain cycles of even length
2. An optimal algorithm for testing whether G is 2-colorable runs in time Θ(|V|+|E|), if G is represented as an adjacency list

Let's break down the logic and explanation for each statement:

1. Understanding 2-Colorability and Cycles:
A graph is 2-colorable if and only if it is bipartite. A fundamental theorem in graph theory states that a graph is bipartite (and thus 2-colorable) if and only if it contains no odd cycles.
Since it cannot contain any cycle of odd length, the statement "If G is 2-colorable, then G may contain cycles of odd length" is false.
However, 2-colorable graphs can definitely contain cycles of even length. For example, a simple cycle graph on 4 vertices (C4) is 2-colorable (we can color alternating vertices with 0 and 1). Thus, the statement "If G is 2-colorable, then G may contain cycles of even length" is true.

2. Testing 2-Colorability Algorithm Complexity:
We can test if a graph G(V, E) is 2-colorable (bipartite) by using a graph traversal algorithm such as Breadth-First Search (BFS) or Depth-First Search (DFS).
During the traversal, we assign colors (0 or 1) to vertices level-by-level. If we encounter an edge between two vertices of the same color, the graph is not 2-colorable. Otherwise, it is 2-colorable.
For a graph represented as an adjacency list, both BFS and DFS visit every vertex and edge of the graph. The time complexity of this traversal is:

Θ ( | V <| + | E <| )

Since we must examine the entire graph in the worst case to determine colorability, this linear time complexity is optimal. Therefore, the statement "An optimal algorithm for testing whether G is 2-colorable runs in time Θ(|V|+|E|), if G is represented as an adjacency list" is true.

Transparent Access on Mindyard

Built for Learners & Educators Alike

Completely free for students. Educators & coaching institutes get 2 months free Pro trial to create tests.

FREE FOR STUDENTS

Practice & Learn Free for Students

Access unlimited practice questions, detailed step-by-step solutions, and exam study materials — completely free for students.

  • Unlimited mock tests & question bank practice
  • Full access to curated study library & formula notes
  • 100% free for students • No credit card required
2 MONTHS FREE TRIAL

Educators & Coaching Institutes

Create and conduct professional online assessments with AI question generation, tab proctoring, and comprehensive batch management.

  • AI question uploader & rapid test generator
  • Anti-cheating tab proctoring & performance reports
  • Full Pro access free for 60 days • No upfront commitment
Discover more resources

You may also like

Mock Tests

View All
  • GATE
  • beginner
  • 3 hours
  • civil engineering

Prepare for GATE 2026 Civil Engineering with the latest question papers, previous year papers, detailed solutions, syllabus, exam pattern, preparation tips, mock tests, and subject-wise study material. Download GATE 2026 CE question papers with solutions in PDF format and boost your preparation for top engineering institutes and PSU recruitment.

  • GATE
  • beginner
  • 3 hours
  • electronics and communication engineering

Prepare effectively for GATE 2026 Electronics & Communication Engineering (EC) with this comprehensive Question Paper with Solutions. This resource includes detailed explanations, concept-wise solutions, previous year paper analysis, and exam-oriented practice to help aspirants strengthen core subjects like Electronic Devices, Analog Circuits, Digital Circuits, Signals & Systems, Network Theory, Control Systems, Electromagnetics, Communications, and more. Perfect for revision, self-assessment, and boosting your GATE 2026 EC preparation strategy.

Ask AI Tutor
5 left
Q1 View Question & Options
AI Tutor is solving this question...
Reading question context & options...
Ask your own doubt or choose a quick prompt: