• S
    SwaseekhGATE Preparation
General
  • Dashboard
  • Syllabus
  • Questions
  • Aptitude
  • Mock Tests
  • TCS NQT 2026
Account
  • Pricing
  • Contact
  1. GATE CS
  2. PYQs
  3. Discrete Mathematics

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 intersect G_2 = (V, E_1 intersect E_2) is not a connected graph, then the graph G_1 union G_2 = (V, E_1 union E_2) A. cannot have a cut vertex B. must have a cycle C. must have a cut-edge (bridge) D. has chromatic number strictly greater than those of G_1 and G_2

GATE 2004 · Discrete Mathematics · Graph Connectivity · medium

Answer: G_1 union G_2 must contain a cycle, which is option B.

  1. The intersection misses some edges: A connected graph on n vertices needs at least n-1 edges. Since G_1 intersect G_2 is disconnected, its edge set E_1 intersect E_2 has at most n-2 edges, so G_1 and G_2 do not share all of their edges.
  2. The union exceeds tree-edge count: Each connected graph contributes >= n-1 edges, while the shared part has <= n-2 edges, so the union has at least n edges on n vertices.
  3. More than n-1 edges forces a cycle: A connected graph with n or more edges on n vertices is not a tree, so it must contain at least one cycle.