Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Graph terminology and special graphs

Basic graph definitions, standard special graphs (complete, bipartite, path, cycle, wheel, star, regular, trees), key theorems (handshaking lemma, complement edge count), examples, common exam mistakes and quick checks.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Graphs model networks: circuits, communication links, dependency graphs, social or transport networks. Engineers use graph terminology to describe structure, count resources (edges, degrees), and recognise special graphs (trees for routing, bipartite graphs for matching problems, complete graphs for worst-case connectivity). Clear terminology speeds proofs and algorithm design (e.g. when using Dijkstra, minimum spanning trees, or checking connectivity).

Key ideas

Start with a set V of objects called vertices (or nodes) and a set E of connections called edges. Below each bolded term is defined when first used.

  • Graph (undirected): an ordered pair G = (V, E) where V is a nonempty finite set of vertices and E is a set of unordered pairs of vertices called edges. By default in basic theory we usually mean a simple graph (see next).

  • Simple graph: a graph with no multiple edges between the same two vertices and no loops (an edge joining a vertex to itself). From now on, unless stated, assume simple graphs.

  • Multigraph: a graph that may have multiple edges between the same pair of vertices (parallel edges) but no loops.

  • Pseudograph: a graph that may have both multiple edges and loops.

  • Order of a graph: the number of vertices |V|. Size of a graph: the number of edges |E|.

  • Adjacency: two vertices u and v are adjacent if there is an edge {u,v} ∈ E. An edge is incident to each of its end vertices.

  • Degree deg(v) (undirected): the number of edges incident to vertex v; a loop contributes 2 to degree.

  • Neighborhood N(v): the set of vertices adjacent to v.

  • Path: a sequence of distinct vertices v0, v1, …, vk with edges {v0,v1}, {v1,v2}, …, {v(k-1),vk}. The path has length k (number of edges) and contains k+1 vertices. We write Pn for a path on n vertices (convention: check your syllabus if they use Pn for n vertices or n edges). A walk allows repeated vertices; a trail is a walk with no repeated edges; a circuit is a closed trail.

  • Cycle: a closed path v0, v1, …, v(k-1), v0 with k ≥ 3, vertices v0 … v(k-1) distinct. Denote Cn for a cycle on n vertices.

  • Connected graph: a graph where for every pair of vertices u and v there exists a path between u and v.

  • Component: a maximal connected subgraph. A subgraph H = (V_H, E_H) of G is a graph with V_H ⊆ V and E_H ⊆ E whose edges have both endpoints in V_H. The induced subgraph G[S] on S ⊆ V has vertex set S and all edges of G with both endpoints in S.

  • Tree: a connected acyclic simple graph. Equivalent statements (useful in proofs): for a graph on n vertices, the following are equivalent: (1) G is a tree; (2) G is connected and has n−1 edges; (3) G is acyclic and has n−1 edges; (4) every pair of vertices is connected by exactly one simple path.

  • Forest: an acyclic graph (each component is a tree).

  • Complete graph K_n: a simple graph on n vertices where every pair of distinct vertices is adjacent. It has n(n−1)/2 edges.

  • Complete bipartite graph K_{m,n}: vertices split in two disjoint sets of sizes m and n; every vertex in the first set is adjacent to every vertex in the second set; no edges within a part. Edges = m·n. A star is K_{1,n} (one centre connected to n leaves). Some books denote star S_n = K_{1,n}; check your course convention.

  • Bipartite graph: vertices partitioned into two sets such that every edge joins vertices from different sets. A graph is bipartite iff it has no odd cycle.

  • Wheel W_n: take a cycle C_{n-1} and add one new central vertex connected to every vertex of the cycle. Wheel W_n has n vertices and 2(n−1) edges (n−1 cycle edges plus n−1 spokes).

  • k-regular graph: every vertex has degree k.

  • Complement Ḡ of a simple graph G on n vertices: Ḡ has the same vertex set and for every pair of distinct vertices u,v, {u,v} is an edge in Ḡ iff it is not an edge in G. Then |E(G)| + |E(Ḡ)| = n(n−1)/2.

  • Isomorphism: graphs G and H are isomorphic if there exists a bijection f between their vertex sets that preserves adjacency: {u,v} ∈ E(G) ⇔ {f(u),f(v)} ∈ E(H). To show isomorphism, give an explicit bijection and check edges.

Important theorem (proved below):

  • Handshaking lemma (degree-sum formula): For any finite undirected graph G = (V,E) (loops counted twice), sum over all vertices of deg(v) = 2·|E|.

Proof (standard): sum the degrees by counting incidences vertex-by-edge. Each edge with distinct endpoints contributes 1 to degree of each endpoint → 2 incidences; a loop contributes 2 to the degree of its single endpoint → 2 incidences. So the total number of incidences equals 2|E|; but total incidences = Σ_{v∈V} deg(v). Thus Σ deg(v) = 2|E|.

Derivations commonly asked:

  • Prove that K_n has n(n−1)/2 edges: count unordered vertex pairs.

  • Prove complement edge-count formula: every unordered pair of vertices is either an edge of G or of Ḡ but not both; there are n(n−1)/2 unordered pairs.

  • Prove tree equivalent statements: show (connected & n−1 edges) ⇒ acyclic by contradiction: if there were a cycle, deleting one edge on it keeps the graph connected but reduces edges below n−1 (impossible). Conversely, (acyclic & n−1 edges) ⇒ connected: otherwise with c ≥ 2 components an acyclic graph has at most n−c edges < n−1.

Diagrams to draw in exam answers (describe exactly):

  1. To illustrate a graph for a worked example: draw 5 labelled vertices {a,b,c,d,e}, place a,b,c in a triangle (a–b–c–a), connect b–d and c–e, label every edge with short ticks to show adjacency, and mark degrees near each vertex: deg(a)=2, deg(b)=3, etc.

  2. To show K_5 and its complement: draw 5 vertices in a pentagon with all diagonals; for complement draw same pentagon but only edges missing from K_5 (none), so Ḡ is the edgeless graph on the same 5 vertices.

Formulas

Σ_{v∈V} deg(v) = 2·|E| — Σ means sum over all vertices v in vertex set V; deg(v) is the (unitless) degree of v; |E| is the number of edges (unitless). Applies to any finite undirected graph; loops counted twice.

|E(K_n)| = n(n−1)/2 — |E(K_n)| is number of edges in complete graph on n vertices; n = |V|. Applies to simple K_n.

|E(K_{m,n})| = m·n — m and n are sizes of the two parts; applies to simple complete bipartite graphs.

|E(G)| + |E(Ḡ)| = n(n−1)/2 — n = |V(G)|; Ḡ is complement; applies to simple graphs.

If G is a tree on n vertices then |E| = n−1 — n is the number of vertices; applies to trees (connected, acyclic simple graphs).

For bipartite G: G has no odd cycle — a structural property (logical equivalence: G is bipartite ⇔ G has no odd cycle).

(Units: graph quantities are unitless counts.)

Worked examples

Example 1 — Degree sum check (step-by-step):

Given simple graph G with vertex set V = {a,b,c,d} and edge set E = {{a,b},{b,c},{c,a},{b,d}}.

Step 1 (list degrees): deg(a) = edges incident to a = {a,b},{a,c} → 2.

deg(b) = {a,b},{b,c},{b,d} → 3.

deg(c) = {b,c},{c,a} → 2.

deg(d) = {b,d} → 1.

Step 2 (sum degrees): Σ deg = 2+3+2+1 = 8.

Step 3 (edge count): |E| = 4.

Step 4 (apply handshaking lemma): 2·|E| = 2·4 = 8 = Σ deg. Check OK.

Example 2 — Identify special graphs and counts:

Question: For n = 6, give edge counts and a short description for K_6, K_{2,4}, C_6, P_6, W_6, and a star S (as K_{1,5}).

Answer (one line each):

K_6: edges = 6·5/2 = 15.

K_{2,4}: edges = 2·4 = 8.

C_6: edges = 6 (a 6-cycle has same number of edges and vertices).

P_6: edges = 5 (path on 6 vertices has 5 edges).

W_6: construct C_5 + central vertex connected to each of the 5 cycle vertices. Vertices = 6. Edges = 5 (cycle) + 5 (spokes) = 10 = 2(6−1).

Star K_{1,5}: edges = 5, centre degree 5, leaves degree 1.

Example 3 — Small proof question (typical exam long question):

Show that a tree on n ≥ 2 vertices has at least two leaves (vertices of degree 1).

Model answer (short proof by induction):

Base n=2: both vertices have degree 1 ⇒ two leaves.

Induction step: assume true for every tree with < n vertices. Let T be a tree with n ≥ 3 vertices. Take a longest path P in T; its end vertices u and v must have degree 1 (if an endpoint had degree >1 we could extend the path), so there are at least two leaves. QED.

(Alternative: since trees have |E| = n−1, the sum of degrees is 2(n−1); if there were at most one vertex of degree 1 and all others had degree ≥ 2, the sum would be ≥ 2n−1, a contradiction. Hence there are at least two degree-1 vertices.)

Common mistakes

  • Confusing number of vertices and path length: path with k edges has k+1 vertices.

  • Not checking whether the graph is simple before applying formulas like n(n−1)/2.

  • Using S_n to denote star without verifying the course convention (some texts use S_n = K_{1,n}, others use different index).

  • Forgetting that K_{m,n} edges = m·n (trying to add intra-part edges too).

  • Misapplying bipartite characterization: showing no odd cycle is necessary and sufficient, but trying to argue with two-colouring without checking all components.

  • For isomorphism, giving a bijection that does not preserve degrees (degree sequence must match); always compare degree multisets first.

For your exam

Typical question types:

  • Definitions: define simple graph, multigraph, loop, degree, path, cycle, tree, forest, complete graph, complete bipartite, complement, regular graph. Full marks: concise definition and 1 short example.

  • Short proofs: Handshaking lemma, proof that tree with n vertices has n−1 edges, bipartite iff no odd cycle. Full marks: clear statements of assumptions, stepwise logic, and conclusion.

  • Derivations and counts: edge counts of K_n, K_{m,n}, W_n. Full marks: show counting argument and final formula.

  • Diagram and labelling: draw a graph with given properties, compute degrees, identify components. Full marks: neat labelled diagram, correct degree counts, and short justification.

  • Isomorphism check: prove or disprove isomorphism between two labelled graphs. Full marks: compare degree sequences, give explicit bijection or contradiction.

  • Small applied problem: identify tree, count leaves, test bipartiteness. Full marks: methodical checks with brief reasoning.

Always state conventions used (e.g. Pn denotes path on n vertices) when the textbook convention is unclear.

Quick check

  1. What is deg(v) if v is incident to one loop and one ordinary edge?
  2. How many edges in K_{3,3}?
  3. Is C_5 bipartite? Explain in one sentence.

Answers: 1) deg(v) = 3 (loop counts 2 + ordinary edge 1). 2) 9. 3) No — C_5 has odd cycle length 5, so not bipartite.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?