Question

A bridge can not be a part of _______

(a) a simple cycle

(b) a tree

(c) a clique with size ≥ 3 whose every edge is a bridge

(d) a graph which contains cycles

The question was asked by my college professor while I was bunking the class.

This interesting question is from Complete and Connected Graphs topic in section Graphs of Discrete Mathematics

Answer 1

Right option is (a) a simple cycle

To explain I would say: In a connected graph, a bridge is an edge whose removal disconnects the graph. In a cycle if we remove an edge, it will still be connected. So, bridge cannot be part of a cycle. A clique is any complete subgraph of a graph.