Answer:
The true statement about the bridge of a graph is:
d. A bridge cannot be part of a simple cycle.
Step-by-step explanation:
Sure, let's break down each statement:
a. **A tree has no bridge.**
- This statement is true. In a tree, every edge is a bridge because removing any edge disconnects the tree into two separate components, making it impossible to travel between them without that edge.
b. **Every edge of a complete subgraph with size greater than or equal 3 is a bridge (A complete subgraph is a subgraph consists of all chosen vertices and its incident edges).**
- This statement is false. In a complete subgraph with size greater than or equal to 3, removing any edge will not necessarily disconnect the subgraph because there are still alternative paths between vertices.
c. **A graph with bridges cannot have a cycle.**
- This statement is false. A graph with bridges can still have cycles. Bridges are edges whose removal would increase the number of connected components in the graph, but they do not prevent the existence of cycles.
d. **A bridge cannot be part of a simple cycle.**
- This statement is true. A simple cycle is a cycle in which no vertex (except the first and last) is repeated. If an edge were to be a bridge in a simple cycle, removing it would disconnect the cycle, contradicting the definition of a cycle.
Therefore, the correct statement is **d. A bridge cannot be part of a simple cycle.**