TOPIC 2 / 2

Graphs, Trees & Discrete Models

Useful preparation: Logic, Sets & Relations

For a long equation, swipe sideways inside its formula box to see every term.

Meaning & notation

Graphs retain connections rather than physical distances. Counting edges and degrees can reveal impossible routes before drawing them.

Finite simple undirected graph: $\displaystyle G = \left(V, E\right)$ has finitely many vertices and unordered edges between distinct vertices, without loops or repeated edges. Degree counts the edges incident to a vertex.
Path, cycle, and tree: A path has no repeated vertices. A cycle returns to its initial vertex without other repetition. A tree is a connected graph with no cycles.
Euler trail: An Euler trail uses every edge exactly once and may revisit vertices. It is an Euler circuit when it ends where it starts; a Hamilton path instead visits every vertex once.

Conditions before calculation

Tree edge counts here concern finite nonempty graphs. Having $\displaystyle \left|V\right| - 1$ edges characterizes a tree only when connectivity is also known.
For an undirected graph with at least one edge, all vertices of positive degree must lie in one connected component for an Euler trail to exist.
Under that connectivity condition, zero odd-degree vertices permit a circuit; exactly two permit an open Euler trail. More than two prevent either.

Why the method works

1. Count every edge twice

Each undirected edge has two endpoints, so summing degrees counts it twice. Consequently the number of odd-degree vertices is even.

\sum_{v\in V}\deg(v)=2|E|

2. Understand tree rigidity

A tree has a unique path between two vertices: two different paths would create a cycle. Removing a leaf removes one vertex and one edge, reducing the edge formula to a smaller tree.

|E|=|V|-1

3. Pair arrivals with departures

At every internal visit of an Euler trail, one unused edge brings the route in and another takes it out. Only distinct starting and ending vertices can have unpaired incidences.

Worked examples

EXAMPLE 1

A graph has vertices A,B,C,D,E and edges AB, BC, CD, DA, AC, CE. Find an Euler trail.

Its degrees are 3,2,4,2,1 respectively. Their sum is 12, confirming that there are six edges.
All vertices are connected; A and E are the only odd-degree vertices, so an open trail must start and end there.
The route E,C,B,A,D,C,A uses EC, CB, BA, AD, DC, CA once each, verifying existence directly.

Conclusion: An Euler trail runs from E to A; no Euler circuit exists.

EXAMPLE 2

A tree has edges AB, AC, BD, BE, CF, CG. Add the new edge DE. Describe the resulting cycle.

The seven vertices are connected by six edges, and the branching structure has no cycle.
The original unique path from D to E is D,B,E. The added edge closes precisely that path.
Deleting DE restores a tree, so every cycle would have to use DE. Uniqueness of the original path leaves only D,B,E,D.

Conclusion: Exactly one cycle is created, with three edges.

Pitfalls & counterexamples

Tempting claim: Any graph with one fewer edge than vertices is a tree.

Correction: The count must be accompanied by connectivity.

Test the claim: A triangle plus an isolated vertex has four vertices and three edges, but is disconnected and contains a cycle.

Check your understanding

If edge AE is added to the first example, can the new graph have an Euler circuit?

Write a reason before opening the explanation. This reflection is not graded or saved.

Compare your reasoning

Yes.

A and E both become even-degree vertices. The graph remains connected and now all degrees are even.

Connect this idea

Degree sums use double counting. Tree arguments invite induction; connectivity converts local degree information into global route guarantees.

Practise this topic →Review concept flashcards

Reference reading

Use these texts to study the underlying definitions and theorems in greater depth. The explanations and examples above are written for Numerive.