Home / COMP2870 / Graph algorithms / Notation worksheet
Notation Worksheet
COMP2870 · Graph algorithms, §1–2
- Use the symbol bar at the bottom of the screen to type ∈ ⊆ ∖ ∅ ∀ … into any box.
- For written answers, write your version first, then open the model answer and mark yourself honestly (✓ / ✗). Your writing is saved in this browser.
- Aim for fluency: redo the parts you got wrong tomorrow, and say each formula aloud.
A · How to say each symbol
Cover the right-hand column and say each one aloud before checking.
| Notation | Say it as | Watch out |
|---|---|---|
| G = (V, E) | "G is the graph with vertex set V and edge set E" | a graph is a pair of sets |
| V(G), E(G) | "the vertex set of G", "the edge set of G" | use these when more than one graph is around (H, T, G…) |
| uv, {u, v} | "the edge uv", "the edge with ends u and v" | in a graph uv = vu; in a digraph they differ |
| v ∈ V, e ∉ E | "v is an element of (is in) V", "e is not in E" | ∈ relates an element to a set |
| A ⊆ B, A ⊂ B | "A is a subset of B", "A is a proper subset of B" | ⊆ relates a set to a set |
| H ⊆ G | "H is a subgraph of G" | it means V(H) ⊆ V(G) and E(H) ⊆ E(G) |
| A ∪ B, A ∩ B, A ∖ B | "A union B", "A intersect B", "A minus B" / "A without B" | ∖ is set difference, not division |
| ∅ | "the empty set" | {∅} is not empty: it has one element |
| {u ∈ V | uv ∈ E} | "the set of all u in V such that uv is in E" | | or : both mean "such that" |
| NG(v) | "the neighbourhood of v in G" | a set of vertices, not a number |
| d(v), |N(v)| | "the degree of v" | a number |
| |V|, |E| | "the number of vertices / edges" (n, m) | |·| on a set means its size |
| G[U] | "the subgraph of G induced by U", "G induced on U" | U must be a subset of V(G) |
| G − S, G − v | "G minus S", "G delete v" | deletes vertices and the edges touching them |
| G − F, G − e | "G minus the edge set F", "G delete e" | deletes edges only |
| T + e | "T plus e" | add an edge (and its ends, if they're new) |
| (u, v)-path | "a u–v path", "a path from u to v" | |
| v0, e1, v1, …, ek, vk | "v-nought, e-one, v-one, up to e-k, v-k" | a walk of length k has k edges and k+1 vertices |
| ∀ x ∈ A | "for every (for all) x in A" | |
| ∃ x ∈ A | "there exists an x in A (such that)" | order matters: ∀∃ ≠ ∃∀ |
| P ⇒ Q, P ⇔ Q | "P implies Q", "P if and only if Q" (iff) | ⇔ needs a proof in both directions |
| w : E → ℕ | "w is a function from E to the natural numbers" | it assigns every edge a weight |
| w(T) = Σe ∈ E(T) w(e) | "w of T is the sum, over the edges e of T, of w of e" | |
| min{ … : … } | "the minimum of … over all … such that …" | |
| □ | "end of proof" (QED) |
B · Read it: formal → English
Write a natural English sentence that someone who has never seen the notation would understand. Then compare.
C · Write it: English → formal
Write each statement in notation, using sets, ∈, ⊆ and quantifiers. There is usually more than one correct answer. Check that yours means the same as the model.
D · Compute with the notation (auto-checked)
V = {1, 2, 3, 4, 5, 6}
E = {12, 23, 34, 14, 15, 35, 36}
Write vertex sets like {1,3} and edge sets like {12, 35}. Use ∅ or {} for the empty set. Order doesn't matter.
E · True or false? (read carefully, every word counts)
G is an arbitrary finite simple graph unless stated otherwise.
F · Complete the definition (auto-checked)
Fill in the blank using the exact wording or notation of the notes.
G · Turn informal reasoning into proof sentences
These are the phrases the lecture-note proofs are built from. Learn them as fixed expressions.
| Let … | introduce a named object: "Let e ∈ E(C)." |
| Suppose / Assume … | start a case or a contradiction: "Suppose that T is not a tree." |
| Since A, B. / By Lemma X, B. | every step names its reason |
| It follows that / Hence / Therefore / So | draw the conclusion |
| We argue by contradiction. | announce the method |
| This contradicts our choice of T. | closes an "extremal choice" argument (fewest edges, most in common, …) |
| w.l.o.g. | "without loss of generality": the other case is symmetric |
| (⇒) … (⇐) … | the two directions of an iff |
| □ | done |
Based on COMP2870 Graph Algorithms Lecture Notes 2026/27 (K. Vušković), §1–2.