Bipartite, Cycle, Regular and Complement Graphs: Tests, Formulas and a C6 Worked Example

The same graph can be bipartite, a cycle graph and regular at once, while its complement can remain regular but stop being bipartite. Memorising four isolated definitions makes these questions look harder than they are. Use a fixed order instead: inspect parity and two-colouring, check whether the whole graph is one cycle, compare every degree, then replace non-edges with complement edges. For C_6, each test can be checked directly.

Bipartite, cycle, regular and complement graphs: definitions and tests

Let G=(V,E) be a finite simple undirected graph. These four ideas answer different questions, so one result should not be used as a shortcut for another.

For an adjacency list or drawing, list the degrees first. Next test for a connected 2-regular graph, try a two-colouring or locate an odd cycle, and finally list the missing unordered pairs. The broader language of paths and colouring is developed in Graph Theory: Euler, Hamiltonian and Coloring for GATE CS.

Bipartite graphs: use two-colouring and the odd-cycle test

A named bipartition is a certificate. Once sets A and B are proposed, check that every edge has one endpoint in each set. Breadth-first or depth-first search performs the same test by assigning opposite colours across each edge. An edge whose endpoints receive the same colour proves failure.

For C_6 with edges {v1v2,v2v3,v3v4,v4v5,v5v6,v6v1}, choose A={v1,v3,v5} and B={v2,v4,v6}. All six edges cross the partition. In C_5, alternation puts v1,v3,v5 in A and v2,v4 in B, but the closing edge v5v1 lies inside A. Therefore C_n is bipartite exactly when n is even. A disconnected graph is bipartite only if every connected component passes this test.

Cycle graphs: separate Cn from a graph that contains a cycle

The cycle graph C_n is defined structurally: it is connected, has n≥3 vertices, has exactly n edges, and gives every vertex degree 2. Bending or crossing edges in a drawing does not change that structure.

Now take H with V={1,2,3,4} and E={12,23,34,41,13}. It contains the cycles 1-2-3-1 and 1-3-4-1, but its degree sequence is (3,2,3,2). It also has 5 edges rather than the 4 edges of C_4, so H is not a cycle graph. Both C_5 and C_6 are connected 2-regular graphs, yet only C_6 is bipartite. Being a cycle graph alone does not settle bipartiteness.

Regular graphs: turn equal degrees into exact edge counts

A graph is k-regular when every vertex has degree k. With n vertices, the degree sum is nk. Each edge contributes 2 to that sum, so 2|E|=nk and therefore |E|=nk/2. This requires nk to be even.

For C_6, n=6 and k=2, giving |E|=(6×2)/2=6. For K_4, each of the 4 vertices has degree 3, so |E|=(4×3)/2=6, matching its six unordered vertex pairs. By contrast, a 3-regular graph on 5 vertices would require (5×3)/2=7.5 edges. Equivalently, its degree sum would be the odd number 15, which cannot equal twice an integer edge count. The parity check rejects impossible claims, but passing it alone is not a construction.

Complement of a graph: count non-edges and transform degrees

The complement bar G uses the same n vertices as G. For every pair of distinct vertices, exactly one of G and bar G contains that edge. Since there are n(n-1)/2 possible unordered pairs,

|E(bar G)| = n(n-1)/2 - |E(G)|.

At a vertex v, the original and complement degrees together cover the other n-1 vertices. Thus deg_barG(v)=n-1-deg_G(v). If G is k-regular, bar G is (n-1-k)-regular. Complementing twice returns the original graph.

The boundary cases check the formulas. The complement of K_4 has 6-6=0 edges and is 0-regular. The complement of the empty graph on four vertices has 6 edges and is K_4, hence 3-regular. No self-loop is created because only distinct vertex pairs are considered.

C6 worked example: classify the graph and compute its complement

Let V={v1,v2,v3,v4,v5,v6} and

E={v1v2,v2v3,v3v4,v4v5,v5v6,v6v1}.

Classify G, then list and classify its complement.

1. Bipartite: A={v1,v3,v5} and B={v2,v4,v6} form a valid bipartition because every listed edge crosses between them.

2. Cycle and regularity: the six edges form one closed chain through all six vertices, so G=C_6. Every vertex has degree 2, making G 2-regular. The handshake calculation gives (6×2)/2=6 edges, agreeing with the list.

3. Complement edge count: six vertices allow 6×5/2=15 unordered pairs. The complement therefore has 15-6=9 edges.

4. Complement edge list: removing the six original pairs leaves

   E(bar G)={v1v3,v1v4,v1v5,v2v4,v2v5,v2v6,v3v5,v3v6,v4v6}.

5. Complement regularity: each complement degree is 6-1-2=3, so bar G is 3-regular. Its degree sum is 6×3=18, and 18/2=9 confirms the edge count independently.

6. Complement bipartiteness: the edges v1v3, v3v5 and v5v1 form the triangle v1-v3-v5-v1. A triangle is an odd cycle, so bar G is not bipartite. A second triangle is v2-v4-v6-v2; the remaining edges v1v4, v2v5 and v3v6 join corresponding vertices of the two triangles.

The conclusion is precise: C_6 is simultaneously bipartite, a cycle graph and 2-regular. Its complement remains regular, but degree 3 rules out a cycle graph and its triangles rule out bipartiteness.

Graph-class traps and the ways questions test them

Four common shortcuts fail on small counterexamples:

• Bipartite means equal part sizes: false. The star K_1,3 has parts of sizes 1 and 3.

• Bipartite implies regular: false. The same star has degrees (3,1,1,1).

• Regular implies bipartite: false. K_3 is 2-regular and contains an odd cycle.

• Containing a cycle means being a cycle graph: false. The earlier graph H has degree sequence (3,2,3,2).

Stable question forms ask you to exhibit a bipartition, find an odd-cycle obstruction, infer an edge count from regularity, transform degrees under complementation, or classify one labelled graph in several ways. Use GATE CS Exam Preparation to place this topic in a broader study route. Then try Graph Theory MCQs: 12 Solved Euler, Coloring and Trees to check whether you can apply the definitions rather than recite them. Our question bank has more than 30 questions on these graph classes for further practice.

Bipartite, cycle, regular and complement graphs: key tests

• Two-colour the graph or find an odd cycle.

• For C_n, verify connectedness and degree 2 at every vertex.

• For regularity, compare every degree and check |E|=nk/2.

• For complements, subtract degrees from n-1 and edges from n(n-1)/2.

Redraw C_6 and its nine complement edges from memory, then verify the two triangles and three cross-edges. Continue with Minimum Spanning Tree for GATE when weighted connected graphs are your next gap. Use Engineering Mathematics for GATE Exam when you want a structured mathematics sequence around graph-theory practice.