Types of Graphs: Finite, Infinite, Null, Trivial and Complete with Worked Examples

Finite and infinite describe the cardinality of a graph’s vertex or edge sets. Null, trivial and complete describe edge structure, so labels can overlap: the one-vertex graph is finite, null, trivial and complete at once. Order, size and adjacency separate the five types, while complements expose every missing simple edge. The Graph Theory for GATE CS: Concepts and Worked Examples map connects these classifications to walks, trees, colouring and planarity, and GATE CS Exam Preparation Courses & Test Series places them within the wider preparation route.

Read every graph through order, size and adjacency

A simple undirected graph is G=(V,E), where each edge is an unordered pair of distinct vertices. Its order is |V|; its size is |E|. With order n, at most C(n,2)=n(n-1)/2 edges are possible because each edge selects two vertices.

Use these graph definitions:

• F: V_F={1,2,3,4}, E_F={{1,2},{2,3},{3,4}}.

• I: V_I={0,1,2,...}, E_I={{i,i+1}: i>=0}.

• N_4: V_N={a,b,c,d}, E_N=empty set.

• T: V_T={x}, E_T=empty set.

• K=K_5: V_K={A,B,C,D,E}, with every unordered pair present.

Thus F is finite only; I is infinite and neither null, trivial nor complete; N_4 is finite and null; T is finite, null, trivial and complete; and K_5 is finite and complete. These labels can overlap for the same graph.

Finite and infinite graphs measure the underlying sets

A finite graph has finite vertex and edge sets. For F, |V_F|=4, |E_F|=3, and the sorted degree sequence is (2,2,1,1). Its degree sum is 6=2 x 3, as the handshaking lemma requires. Every listed null, trivial or complete graph of specified finite order is also finite.

An infinite graph has infinite V or E. Graph I is the one-way path 0-1-2-3-..., with countably infinitely many vertices and edges. Here deg(0)=1, while deg(i)=2 for every integer i>=1. An infinite graph need not have a vertex of infinite degree.

For a simple graph, finite |V|=n forces |E|<=C(n,2), so its edge set cannot be infinite. Other models may allow different multiplicities; follow the stated model.

Null and trivial graphs differ by order

Here, null means edgeless, so E=empty set; a finite edgeless graph of order n is N_n. Some books reserve “null graph” for a graph with no vertices. In a question, use its definition and state |V| and |E| explicitly.

For N_4, order is 4, size is 0, and the degree sequence is (0,0,0,0). It is finite and null, not trivial because its order is not 1, and not complete because {a,b}, for example, is not an edge.

A trivial graph has order 1. For T, order is 1, size is 0, and deg(x)=0. It is N_1 under our convention and also K_1: there is no pair of distinct vertices that violates completeness. This is vacuous truth. Thus T=N_1=K_1.

Complete graphs contain every possible simple edge

In K_n, every pair of distinct vertices has exactly one edge. Therefore |E(K_n)|=C(n,2)=n(n-1)/2, and every vertex has degree n-1. Division by two corrects the double count from endpoints.

For K=K_5,

E={AB,AC,AD,AE,BC,BD,BE,CD,CE,DE}.

So |E|=C(5,2)=5 x 4/2=10. Every degree is 4, and 4+4+4+4+4=20=2 x 10 verifies the count. Delete only CD: the new size is 9; deg(C)=deg(D)=3; and deg(A)=deg(B)=deg(E)=4. It is not complete because C,D are non-adjacent.

Conversely, if every vertex in a complete graph has degree 9, then n-1=9, so it is K_10 with 10 x 9/2=45 edges. Engineering Mathematics for GATE Exam can strengthen the counting used here.

Use complements to connect null and complete graphs

For a simple graph on a fixed vertex set, two distinct vertices are adjacent in complement(G) exactly when they are not adjacent in G. Both graphs share V, and their sizes add to C(n,2).

The complement of N_4 has edges {ab,ac,ad,bc,bd,cd}, so complement(N_4)=K_4 and 0+6=C(4,2)=6. Conversely, complement(K_4)=N_4.

For K_5-CD, the complement has size 10-9=1 and exactly edge CD; A,B,E are isolated. Thus “not complete” does not mean “null”.

Classify graphs with a fixed decision sequence

First ask whether V and E are finite. Record order and size. If size is 0, test the stated null convention; if order is 1, mark trivial. Finally compare adjacency and size with C(n,2). The equality proves completeness only in the simple undirected model.

For a boundary case, let J have V_J={0,1,2,...} and E_J=empty set. It is infinite and edgeless, hence null under our convention, but neither trivial nor complete. A book with a narrower definition may call J only edgeless.

Avoid the traps that make answers look correct

The names are not exclusive: K_1=N_1 has four labels. Not every null graph is trivial, as N_4 shows. A crossing-free drawing does not prove completeness; inspect every pair. A long drawing is not necessarily infinite; its sets decide. Nine edges do not make K_5-CD complete because pair C,D is missing.

Check three corrections:

• Order 6, size 0: N_6, finite and null, neither trivial nor complete.

• Complete graph of order 8: 8 x 7/2=28 edges, degree 7 at each vertex.

• complement(N_6)=K_6, with 6 x 5/2=15 edges.

Practise the distinctions, then take the next step

Try this speed drill:

1. V={p}, E=empty set: finite, null, trivial and complete, by the same K_1 reasoning.

2. Order 7, every degree 6: K_7, with 7 x 6/2=21 edges.

3. Order 8, size 27: not complete, because C(8,2)=28.

4. V={0,1,2,...}, E={{i,i+1}:i>=0}: infinite, non-null, non-trivial and non-complete.

Objective questions may supply order, size, a degree, a missing edge or a complement and ask for valid labels or counts. Continue with Graph Theory MCQs: 12 Solved Euler, Coloring, Trees for practice.

The short version is simple: finite or infinite asks about set size; null asks whether edges are absent; trivial asks whether exactly one vertex exists; complete asks whether every distinct pair is adjacent. Redraw N_4, K_1 and K_5-CD, label order and size, then classify them without notes. For a wider structured path, use GATE Guidance by Sanchit Sir.