Planar Graphs and Euler's Formula for GATE: Planarity Checks, Matching and Vertex Covers Solved

Graph-theory numericals often turn on one condition hidden inside a familiar formula. Knowing V - E + F = 2 is not enough if you forget the outer face or apply the wrong edge bound. Exact small graphs count faces, disprove planarity and connect a bipartite matching to a minimum vertex cover.

Euler's formula and what a face means

A graph is planar if it can be drawn in the plane without any edges crossing except at a shared endpoint. A particular crossing-free drawing is called a planar embedding.

For a connected planar graph:

V - E + F = 2

Here V is the number of vertices, E is the number of edges, and F is the number of faces in the embedding. Faces are regions bounded by edges. The unbounded region around the drawing is also a face, so it must be counted.

For the common face-count question, rearrange once:

F = 2 - V + E

Consider K4, the complete graph on four vertices. It has V = 4 and E = 6. It is planar: draw three vertices as a triangle and put the fourth inside, joining it to all three corners. Euler's formula gives:

F = 2 - 4 + 6
  = 4

The embedding has three bounded triangular faces and one outer face. Counting only the triangles would give the wrong answer, 3.

Edge bounds that can disprove planarity

Euler's formula leads to a useful bound. Every connected simple planar graph with V >= 3 satisfies:

E <= 3V - 6

If the graph is triangle-free, every face boundary has length at least four. A simple bipartite graph is triangle-free, so the tighter bound applies:

E <= 2V - 4

Both conditions are necessary, not sufficient. If a graph violates the applicable bound, it is definitely non-planar. If it satisfies the bound, you still need an embedding or another theorem to prove planarity.

K4 reaches the general bound exactly:

3V - 6 = 3(4) - 6 = 6 = E

Its six edges cannot be increased while keeping a simple planar graph on those four vertices, so it is maximal planar.

Worked planarity checks on K5 and K3,3

For K5, every pair among five vertices is joined. Therefore V = 5 and E = 10. Apply the general simple-planar bound:

3V - 6 = 3(5) - 6
         = 15 - 6
         = 9

Because 10 > 9, K5 is non-planar.

For K3,3, place three vertices in each part and join every vertex on one side to every vertex on the other. It has V = 6 and E = 3 x 3 = 9. Since it is bipartite, use the tighter bound:

2V - 4 = 2(6) - 4
         = 12 - 4
         = 8

Because 9 > 8, K3,3 is also non-planar. Using only 3V - 6 would give 9 <= 12, which proves nothing. This is why recognising bipartiteness matters.

Kuratowski's theorem gives the deeper characterization: a finite graph is planar exactly when it contains no subdivision of K5 or K3,3 as a subgraph. These two graphs are therefore the standard witnesses behind many planarity arguments. For the wider vocabulary of paths, colouring and connectivity, use Graph Theory: Euler and Hamiltonian Paths, Coloring and Connectivity.

Matching, vertex cover and Konig's theorem

A matching is a set of edges with no shared endpoint. A maximum matching contains as many edges as possible. A vertex cover is a set of vertices that touches every edge, and a minimum vertex cover uses as few vertices as possible.

In any graph, the size of a maximum matching is at most the size of a minimum vertex cover. In a bipartite graph, Konig's theorem strengthens that inequality to equality.

Take left set {a, b, c}, right set {x, y}, and edges:

a-x, a-y, b-x, c-y

Choose the matching {b-x, c-y}. The two edges share no endpoint, so this is a valid matching of size 2. A matching cannot have size 3 because the right part contains only two vertices. The maximum matching size is therefore exactly 2.

Now choose vertex cover {x, y}. Every edge ends at either x or y, so all four edges are covered. No single vertex can cover both disjoint matching edges b-x and c-y; therefore a cover of size 1 is impossible. The minimum vertex cover size is exactly 2.

Thus the worked graph gives:

maximum matching size = 2 = minimum vertex cover size

Traps GATE plants in these questions

First, count the outer face. Second, check connectedness before using V - E + F = 2. For a planar graph with c connected components, the correct relation is V - E + F = 1 + c.

Do not use an edge bound backwards. Failing a necessary bound proves non-planarity; passing it does not prove planarity. Also reserve E <= 2V - 4 for simple triangle-free graphs with at least three vertices, including the bipartite cases usually seen here.

Konig's equality is restricted to bipartite graphs. The odd cycle C5 shows why: its maximum matching has size 2, while its minimum vertex cover has size 3.

Keep this topic separate from spanning trees. A matching selects mutually disjoint edges, while a spanning tree connects every vertex. Minimum Spanning Tree for GATE: Kruskal and Prim Numericals with Unique-MST Questions handles that second problem.

How GATE tests planar graphs and matching

Common stems ask for the number of faces in a known planar embedding, whether a graph can be planar, the size of a maximum matching or the size of a minimum vertex cover. A mixed question may first establish planarity and then ask for F.

More than 1,300 Discrete Mathematics practice questions cover graph counting, Euler bounds, matching and vertex-cover work. For a year-specific question or marking rule, check the official GATE portal of the organising IIT.

Short version and next step

Use V - E + F = 2 only for connected planar graphs and include the outer face. Use E <= 3V - 6 for simple planar graphs and E <= 2V - 4 when triangle-free. A violated bound disproves planarity. In a bipartite graph, maximum matching size equals minimum vertex cover size.

Practise the checks in mixed order, then time the same decisions in the GATE Test Series. The broader GATE preparation category can help you place graph theory beside the rest of Discrete Mathematics.