Graphs / Trees
Least You Need to Know: Trees
A tree is a connected graph with **no cycles**. In a tree with n vertices, the number of edges is always n-1.
جو کم از کم جاننا ضروری ہے
- A tree is connected and acyclic.
- A graph with n vertices and n-1 edges is a tree if it is connected.
- Adding one edge to a tree creates exactly one cycle.
- Removing one edge from a tree disconnects it.
اہم علامتیں
n
number of vertices
n-1
edge count in a tree
leaf
vertex of degree 1
مختصر حل شدہ مثال
- A tree has 7 vertices.
- Then it has 6 edges.
- If you add one new edge between two existing vertices, you create one cycle.
عام غلطیاں
- Students often memorize n-1 but forget the graph also has to be connected.
- Students often call any acyclic graph a tree even if it has multiple components.
- Students often forget leaves have degree 1, not 0.
اس قسم کے سوال کو کیسے پہچانیں
- If the graph is not connected, it is not a tree.
- Count vertices first, then compare with edges.
- Ask whether there is exactly one simple path between two vertices.
Next recommended lesson
Try Least You Need to Know: Basic Graphs next for a nearby refresher.
Least You Need to Know: Basic GraphsRelated lessons
Keep going with nearby lessons in the same topic.