# Graphs and Trees

Computer Science I · Discrete Mathematics · https://tryals.app/learn/computer-science-i/graphs-and-trees

## Modeling Connections

A **graph** is a set of **vertices** joined by **edges**, modeling anything from road maps to social networks. 

| Term | Definition | Example / Rule |
| --- | --- | --- |
| **Degree** | Incident edges on a vertex | Sum of degrees = $2|E|$ |
| **Path** | Sequence of connected vertices | Can lead to a **cycle** |
| **Connected** | Path exists between all pairs | Isolated nodes disconnect it |
| **Directed** | One-way edges (**digraph**) | Unlike **undirected** edges |

The **handshaking lemma** states $\sum \deg(v) = 2|E|$ because each edge connects two endpoints. **Corollary:** odd-degree vertices are always even in number.

## Trees & Pitfalls

A **tree** is a special graph defined as **connected and acyclic**. On $n$ vertices, a tree has **exactly $n-1$ edges** and a unique path between any two nodes.

| Graph Type | Connected? | Acyclic? | Edge Count |
| --- | --- | --- | --- |
| **Tree** | Yes | Yes | $n - 1$ |
| **Forest** | No | Yes | $< n - 1$ |
| **Cycle Graph**| Yes | No | $n$ |

> **Common Pitfall:** Forgetting that $\sum \deg(v)$ equals _twice_ the edges, not $|E|$ alone. A tree must be **both** connected and acyclic; disconnected acyclic graphs are **forests**.

## Practice questions

5 of this lesson's 9 practice questions, with answers. The full set is in the app.

### 1. A social network is a graph, a filesystem is a tree, and a tree is a graph. What does the extra restriction buy the filesystem?

A. Guarantees that simplify algorithms: one path, no cycles, n−1 edges
B. Faster access, since trees are always balanced
C. The ability to represent hierarchical data, which graphs cannot
D. More storage efficiency, since trees use fewer pointers than graphs

**Answer:** A. Guarantees that simplify algorithms: one path, no cycles, n−1 edges

**Why:** No cycles means recursive traversal terminates without tracking visits, and a unique path means one canonical location per file. Symbolic links break the guarantee and reintroduce exactly those problems, which is why `find` has loop detection and why the restriction is worth having.

Page: https://tryals.app/practice/computer-science-i/graphs-and-trees/a-social-network-is-a-graph-a-filesystem-is-a-tree-and-a-tree-is-a

### 2. Select every statement that must be true of any tree with n vertices.

A. There is exactly one path between any two of its vertices
B. Every vertex has degree at least 2
C. It is connected
D. It has exactly n minus 1 edges
E. It contains at least one cycle

**Answer:** A. There is exactly one path between any two of its vertices; C. It is connected; D. It has exactly n minus 1 edges

**Why:** A tree is connected and acyclic, which gives exactly n - 1 edges and a unique path between any two vertices, a second path would close a cycle. It contains no cycle at all, and its leaves have degree 1, so a three-vertex path graph refutes the second option immediately.

Page: https://tryals.app/practice/computer-science-i/graphs-and-trees/select-every-statement-that-must-be-true-of-any-tree-with-n-vertices

### 3. Sort each term or description by what it is a property of.

**Answer:**

- A property of a single vertex: Degree, The number of edges meeting at this point
- A description of a path or cycle: A route that returns to the vertex it started from, A sequence of vertices in which each is joined to the next by an edge
- A property of the whole graph: Connected, Acyclic

**Why:** Degree is local, measured at one vertex. Paths and cycles are routes through the graph. Connectedness and acyclicity are global: you cannot confirm either by inspecting one vertex. Sorting terms this way is the fastest way to keep graph vocabulary straight, because the level a term lives at determines what you must examine to test it.

Page: https://tryals.app/practice/computer-science-i/graphs-and-trees/sort-each-term-or-description-by-what-it-is-a-property-of

### 4. The handshaking lemma says the degrees of all vertices sum to twice the number of edges. Why must the total be even, and what does that immediately rule out?

A. Because degrees are counted twice by convention, and the convention could have been otherwise.
B. Because every graph must have an even number of vertices.
C. Because loops contribute 2 to a vertex's degree, and loops are required in every graph.
D. Because each edge adds 2 to the sum, so the degree sum is always even.

**Answer:** D. Because each edge adds 2 to the sum, so the degree sum is always even.

**Why:** Each edge has two endpoints and adds 1 to each, contributing exactly 2, so the sum is always even whatever the graph looks like. Odd numbers sum to an even total only in even quantity, so a graph with exactly three odd-degree vertices does not exist. It underlies Euler's theorem: a closed circuit needs every degree even, an open trail exactly two odd, never one.

Page: https://tryals.app/practice/computer-science-i/graphs-and-trees/the-handshaking-lemma-says-the-degrees-of-all-vertices-sum-to-twice

### 5. A connected graph with 8 vertices and 8 edges must contain a cycle.

**Answer:** True

**Why:** True. A tree on n vertices has exactly n − 1 edges, so a connected graph with 8 vertices and 7 edges is a tree; the 8th edge joins two already-connected vertices and closes a cycle. Any connected graph with n or more edges is therefore cyclic, which is how cycle detection can start from a count.

Page: https://tryals.app/practice/computer-science-i/graphs-and-trees/a-connected-graph-with-8-vertices-and-8-edges-must-contain-a-cycle