Question

Which type of graph does not contain any cycles?

• A. Complete graph
• B. Directed graph
• C. Tree
• D. Weighted graph

Hint:

For any connected graph with $V$ vertices, if it has exactly $V-1$ edges, it is guaranteed to be a tree and therefore contains no cycles.

Answer 1

The Correct Option is C

Concept: A cycle is a path of edges and vertices wherein a vertex is reachable from itself.
• Acyclic: A graph that contains no cycles.
• Tree: A connected acyclic undirected graph.
• Forest: A collection of disjoint trees (an acyclic graph that may be disconnected).

Step 1: Defining a Tree in Graph Theory.
A tree is defined by two mandatory properties. First, it must be connected (a path exists between any two vertices). Second, it must be acyclic (no loops or cycles).

Step 2: Analyzing other graph types.
A Complete Graph (A) has an edge between every pair of vertices, so it is full of cycles. A Directed Graph (B) can easily contain cycles (Directed Acyclic Graphs or DAGs are a special subset). A Weighted Graph (D) simply adds costs to edges; it can be cyclic or acyclic.

Step 3: Conclusion.
By definition, a Tree is the only graph type in this list that is guaranteed to be acyclic.