Computer Sciences > GATE 2015 SET-2 > Graph Theory
In a connected graph, a bridge is an edge whose removal disconnects a graph. Which one of the following statements is true?
A
A tree has no bridges.
B
A bridge cannot be part of a simple cycle.
C
Every edge of a clique with size ≥ 3 is a bridge. (A clique is any complete subgraph of a graph.)
D
A graph with bridges cannot have a cycle.

Correct : b

Similar Questions

Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time on Depth First Search of G? Assume that the graph is represen...
#14 MCQ
Let G=(V,E) be a directed graph where V is the set of vertices and E the set of edges. Then which one of the following graphs has the same strongly connected co...
#18 MCQ
In an adjacency list representation of an undirected simple graph G = (V, E), each edge (u, v) has two adjacency list entries: [v] in the adjacency list of u, a...
#91 MCQ

Related Topics

computer science gate 2015 tree graph bridge in graph theory GATE computer sciences simple cycles graph clique graph complete subgraph graph theory bridges no cycle with bridge graph connectivity GATE set 2 2015

Unique Visitor Count

Total Unique Visitors

Loading......

Question Options

Contributed by: