Graph Theory for GATE CS: Concepts and Worked Examples

Graph theory questions can look like a collection of unrelated terms: degree, path, tree, planar graph, colouring, Euler, and Hamilton. The difficulty reduces when the same small graph connects those ideas. Two small graphs are enough to settle all of them for GATE CS preparation: a six-vertex graph $G$ with seven edges, and a six-cycle $H$ carrying one chord. Every degree, bridge, spanning tree, colouring and face count comes straight off those two edge lists, so keep them beside you.

1. Graph basics: the language every solution needs

A graph is written as $G=(V,E)$, where $V$ is its vertex set and $E$ is its edge set. Its order is $n=|V|$, and its size is $m=|E|$. Two vertices are adjacent when an edge joins them. A vertex and an edge are incident when that edge touches the vertex. The degree counts incident edge ends. A loop begins and ends at the same vertex, while parallel edges join the same pair more than once.

Our main graph is finite, simple, and undirected:

$$V=\{A,B,C,D,E,F\},\qquad E=\{AB,AC,BC,BD,CE,DE,EF\}.$$

Thus $n=6$ and $m=7$. Its edges are unordered pairs, with no loops or parallel edges. An edge list is compact for calculation, an adjacency list records each vertex's neighbours, and an adjacency matrix gives a square lookup table. Because $G$ has only seven edges, every claim about it can be settled by reading that list line by line.

2. Degree, edge count, and the complement of a graph

Read each degree directly from the seven edges:

• $A$ touches $AB,AC$, so $\deg(A)=2$.

• $B$ touches $AB,BC,BD$, so $\deg(B)=3$.

• $C$ touches $AC,BC,CE$, so $\deg(C)=3$.

• $D$ touches $BD,DE$, so $\deg(D)=2$.

• $E$ touches $CE,DE,EF$, so $\deg(E)=3$.

• $F$ touches only $EF$, so $\deg(F)=1$.

The degree sum is

$$2+3+3+2+3+1=14=2m=2\times 7.$$

This verifies the handshaking lemma. The odd-degree vertices are $B,C,E,F$, four in total, which is correctly an even number.

A simple undirected graph on six labelled vertices can contain at most

$$\binom{6}{2}=\frac{6\times 5}{2}=15$$

edges. The complement $\overline G$ therefore has $15-7=8$ edges. At $A$, the complement-degree rule gives $\deg_{\overline G}(A)=5-\deg_G(A)=5-2=3$. Indeed, $A$ is not adjacent to $D,E,F$ in $G$, so those are exactly its three complement neighbours.

3. Walks, trails, paths, cycles, and connectivity

A walk is any sequence of vertices in which each consecutive pair is joined by an edge, and both vertices and edges may repeat. So $A-B-C-A-B$ is a walk in $G$, even though it reuses edge $AB$ and revisits $A$ and $B$. Trails, paths and cycles are walks with restrictions added.

Check each sequence against repeated edges first, then repeated vertices. $A-B-C-E-D-B$ uses the edges $AB,BC,CE,ED,DB$ once each, so it is a trail. It is not a path because vertex $B$ repeats. By contrast, $F-E-C-A$ is a path because every vertex, and therefore every used edge, is distinct. The sequence $A-B-C-A$ returns to its starting vertex without repeating another vertex, so it is a cycle.

The graph is connected, but some single removals can disconnect it. Removing $EF$ isolates $F$, so $EF$ is a bridge. Removing vertex $E$, together with its incident edges, also isolates $F$, so $E$ is an articulation vertex. However, $DE$ is not a bridge. If it is removed, $D$ can still reach $E$ along $D-B-C-E$. Connectivity must be checked using an alternative route, not by judging how important an edge looks in a drawing.

4. Trees and spanning trees from a connected graph

A tree is connected and acyclic. A tree with $n$ vertices has $n-1$ edges, and every pair of its vertices has one unique simple path between them. The edge count alone is not sufficient: a disconnected graph with a cycle can also have $n-1$ edges. Pair the count with connectivity or acyclicity.

For $G$, take

$$T=\{AB,AC,BD,CE,EF\}.$$

This subgraph contains all six vertices, has five edges, and is connected. It is therefore a spanning tree. The omitted edges are $BC$ and $DE$. Each would close a cycle if restored, so removing them preserves connectivity while eliminating cycles. Edge $EF$ cannot be omitted from any spanning tree of $G$, because it is the only edge incident on $F$ and is already a bridge.

5. Bipartiteness, colouring, and planar faces

Now define a second graph $H$ by

$$V(H)=\{1,2,3,4,5,6\},\qquad E(H)=\{12,23,34,45,56,61,25\}.$$

It is a six-cycle with chord $25$. Use the partition

$$X=\{1,3,5\},\qquad Y=\{2,4,6\}.$$

Every listed edge has one endpoint in $X$ and one in $Y$, including the chord $25$. Hence $H$ is bipartite. Colour all vertices in $X$ blue and all vertices in $Y$ orange to get a proper two-colouring. Its chromatic number is exactly $2$: two colours suffice, and one cannot suffice because the graph has edges.

In the planar embedding drawn below, $n=6$, $m=7$, and $f=3$, where the faces are the two bounded regions and the outer face. Euler's planar formula checks the count:

$$n-m+f=6-7+3=2.$$

This formula concerns vertices, edges, and faces in a connected planar embedding. It is different from an Euler trail or Euler circuit, which asks for a traversal using every edge exactly once.

6. How GATE CS questions combine graph theory concepts

A problem may ask you to reconstruct an edge count from degrees, decide whether a degree sequence is graphical, identify a bridge or articulation vertex, choose a spanning tree, or test bipartiteness and planarity. Another common reasoning split is between Euler conditions and Hamilton conditions. Treat each as a request for a specific property, then apply only the relevant test.

For $G$, the four odd-degree vertices $B,C,E,F$ mean that the connected graph has neither an Euler circuit nor an Euler trail. A circuit requires zero odd-degree vertices, while a trail requires exactly two. The leaf $F$ rules out a Hamiltonian cycle, because a vertex on such a cycle needs two cycle edges. One Hamiltonian path does exist, however:

$$F-E-D-B-A-C$$

The edges $FE,ED,DB,BA,AC$ are all in $G$, and the sequence visits every vertex exactly once. For the same concepts pushed further, read Graph Theory: Euler and Hamiltonian Paths, Coloring and Connectivity. For the same ideas in question form, work through Graph MCQs: 10 solved questions on representations, BFS, DFS and connectivity.

7. Graph theory traps that cost correct answers

First identify the graph type. A loop contributes two to the degree of its vertex, not one, and formulas for simple graphs may fail on a multigraph. Next, keep walk, trail, and path separate: check repeated edges for a trail, then repeated vertices for a path.

Do not transfer Euler's degree criterion to Hamilton questions. Write two prompts on the page: “uses every edge” for Euler, and “visits every vertex” for Hamilton. Similarly, do not declare a graph a tree merely because it has $n-1$ edges. Verify that it is connected and acyclic. For Euler's planar formula, count every face, including the unbounded outer face. These short checks prevent a correct calculation from being attached to the wrong definition.

8. Graph theory recall chain and your next practice step

Use this recall chain: identify the graph type, write $V$ and $E$, compute degrees and $2m$, inspect cycles and cuts, then test the required tree, bipartite, or planar condition. Finally, separate edge-covering Euler questions from vertex-covering Hamilton questions.

If you need full subject sequencing, continue with GATE Guidance by Sanchit Sir. If you have revised the concepts and want timed practice, use the GATE Test Series. KnowledgeGate's practice bank also holds more than 350 graph theory questions, so your next step can be simple: revise one condition, solve a set, and explain every rejected option.