Wheel Graph in Discrete Mathematics: W6 Representation, Logic Encoding and Exam Patterns

Build one labelled W6 from its rim and spokes, then verify the same graph through degrees, a matrix, logical formulas, colouring and quick decisions.

KnowledgeGate Team

Exam prep & CS education

Updated 12 Nov 20266 min read
Wheel Graph in Discrete Mathematics: W6 Representation, Logic Encoding and Exam Patterns

A wheel is easy to recognise in a picture, but notation varies across books. The same graph can also look unfamiliar when a question supplies an edge list, adjacency matrix or logical formula instead of a drawing. For a fixed W6, the edge list and adjacency matrix encode the same 10 edges, while propositional and predicate formulas state exactly the same adjacency relation. Review propositional and predicate logic fundamentals if needed. Logic describes adjacency here; it does not change the graph.

1. What a wheel graph is, and why the subscript can mislead

The convention is

W(n) = K1 + C(n-1), for n >= 4.

The join means taking one isolated hub vertex, taking a cycle on n-1 rim vertices, and adding an edge from the hub to every rim vertex. Under this convention, the subscript counts all vertices, so |V(W(n))|=n.

The rim contributes n-1 edges and the spokes contribute another n-1. Therefore,

E(W(n))

=(n-1)+(n-1)=2(n-1).

The hub has degree n-1, while each rim vertex has degree 3, from two rim neighbours and the hub.

Some texts instead define W(n)=K1+C(n). There the subscript counts rim vertices, and the graph has n+1 total vertices. Always read the definition before using a formula.

Two boundary facts are useful. Under the convention, W4=K4. Every wheel is connected and planar: every rim vertex reaches the hub, and the rim cycle can be drawn around it without crossings.

2. Build and verify the worked wheel W6

Under the total-vertex convention, W6=K1+C5. Fix

V={h,v1,v2,v3,v4,v5}.

The rim edges are v1v2,v2v3,v3v4,v4v5,v5v1. The spokes are hv1,hv2,hv3,hv4,hv5. We therefore have 6 vertices and 5+5=10 edges.

The hub touches all five rim vertices, so degree(h)=5. Every vi touches the hub and its two neighbours on the rim, so degree(vi)=3 for i in {1,2,3,4,5}. The handshaking lemma confirms the count:

5+5 x 3=20=2 x 10.

There are exactly five hub triangles, h-vi-v(i+1)-h, with indices modulo 5. The last is h-v5-v1-h. The five non-edges among distinct rim vertices are v1v3,v1v4,v2v4,v2v5,v3v5. None is a hidden diagonal.

Wheel graph W6 has six vertices, ten edges, a degree-five hub, degree-three rim vertices, and one highlighted hub triangle.

3. Read the same wheel as an adjacency matrix

Keep the order h,v1,v2,v3,v4,v5. The matrix is:

h

v1

v2

v3

v4

v5

h

0

1

1

1

1

1

v1

1

0

1

0

0

1

v2

1

1

0

1

0

0

v3

1

0

1

0

1

0

v4

1

0

0

1

0

1

v5

1

1

0

0

1

0

Symmetry about the main diagonal shows that the graph is undirected. The zero diagonal shows that it has no loops. The row sums are 5,3,3,3,3,3, exactly the degrees already calculated. All entries sum to 20. Dividing by 2, because each undirected edge occurs twice, recovers 20/2=10 edges.

Individual lookups recover the picture too. A[h,v4]=1 because hv4 is a spoke. A[v1,v5]=1 because the rim closes. A[v1,v3]=0 because that diagonal is absent.

4. Encode the exact edge set in propositional logic

There are 6 choose 2=15 unordered pairs of distinct vertices. Give each pair one Boolean variable e(x,y), true exactly when x and y are adjacent. Since the graph is undirected, e(h,v1) and e(v1,h) are not separate variables.

The exact propositional encoding uses all 15 unordered pairs:

Phi(W6) is the conjunction of these three lines:

(e(h,v1) AND e(h,v2) AND e(h,v3) AND e(h,v4) AND e(h,v5))

AND (e(v1,v2) AND e(v2,v3) AND e(v3,v4) AND e(v4,v5) AND e(v5,v1))

AND (NOT e(v1,v3) AND NOT e(v1,v4) AND NOT e(v2,v4) AND NOT e(v2,v5) AND NOT e(v3,v5)).

The ten positive literals force all five spokes and all five rim edges. The five negative literals exclude every remaining pair, so a satisfying assignment represents exactly this labelled W6.

For example, e(h,v2) AND NOT e(v2,v5)=1 AND 1=1. By contrast, e(v1,v3) OR e(v2,v5)=0 OR 0=0. Listing only the positive literals is incomplete unless the question separately states that no other edges exist, because extra rim diagonals would still be allowed.

5. Express the wheel with a predicate adjacency relation

Use the domain {h,v1,v2,v3,v4,v5}, a unary predicate Rim(x), and a binary predicate E(x,y). Define

Rim(x) <-> (x=v1 OR x=v2 OR x=v3 OR x=v4 OR x=v5).

For a simple undirected graph, two conditions apply: NOT E(x,x) for every x, and E(x,y) <-> E(y,x) for every x and y.

Let Cycle5(x,y) be true for exactly these ordered pairs:

(v1,v2), (v2,v1), (v2,v3), (v3,v2), (v3,v4),

(v4,v3),(v4,v5),(v5,v4),(v5,v1),(v1,v5).

Then the exact adjacency relation is

For every x and y, E(x,y) <-> ((x = h AND Rim(y)) OR (y = h AND Rim(x)) OR Cycle5(x,y)).

E(h,x) is true for every rim vertex x because the hub reaches all five rim vertices. However, E(x,y) is not true for every pair of distinct rim vertices. The pair x=v1, y=v3 is a counterexample: universal rim adjacency would describe a complete rim, not a cycle.

6. Derive colouring and cycle facts from the representation

Under the convention W(n)=K1+C(n-1), the rim length is n-1. If n is odd, the rim length is even. Two colours can alternate around the rim, and the hub needs a third, giving chi(W(n))=3. If n is even, the rim length is odd and requires three colours. The hub touches every rim colour class, so it requires a fourth, giving chi(W(n))=4.

For W6, the rim is C5. One proper rim sequence is red, blue, green, red, blue on v1 through v5, followed by yellow on h. Thus chi(W6)=4. For W7, the rim is C6. Alternate red and blue on v1 through v6, then use yellow for h, so chi(W7)=3.

Side-by-side coloring comparison shows W6 with chromatic number four and W7 with chromatic number three, using odd and even rims respectively.

The rim is a cycle through every rim vertex, but it omits the hub. The sequence h-v1-v2-...-v(n-1)-h is a Hamiltonian cycle of the full wheel. The n-1 hub triangles also show immediately that a wheel cannot be bipartite.

7. Exam-style decisions and the traps behind them

Use a four-check routine:

  1. Identify whether the subscript counts total vertices or rim vertices.

  2. Separate rim edges from spokes.

  3. Verify the count using row sums or the handshaking lemma.

  4. Translate every logical quantifier and connective literally.

Then practise the decisions with solved Graph Theory MCQs. The GATE Test Series is an optional next step for timed practice.

Consider a question that explicitly defines W8=K1+C7, using the total-vertex convention. It has 8 vertices and 2(8-1)=14 edges. The hub degree is 7, and each of the seven rim vertices has degree 3. The degree sum check is

7+7 x 3=28=2 x 14.

Because C7 is odd, chi(W8)=4. Every rim vertex is adjacent to h, while not every pair of distinct rim vertices is adjacent.

Four common traps now become easy to reject. Under the alternative W(n)=K1+C(n) convention, a wheel built from C6 has 7 total vertices and 6+6=12 edges, not the 6 vertices and 10 edges of W6 under the total-vertex convention. A fan uses a path, so its rim does not close into a cycle. Spokes such as hv1 and hv3 do not create the diagonal v1v3. Finally, positive edge literals do not forbid unlisted edges.

8. The short version and the next step

Under the declared convention, W(n)=K1+C(n-1). It has n vertices, 2(n-1) edges, hub degree n-1, and rim degree 3. An edge list, adjacency matrix, propositional atoms and the predicate E(x,y) all encode the same relation. For colouring, test the parity of the rim length rather than blindly using the wheel subscript.

As a mastery check, reconstruct the W6 edge list, matrix and Phi(W6) from an unlabelled picture. Your row sums should be 5,3,3,3,3,3, and they should recover 10 edges. For a structured path through the wider subject, use GATE Guidance by Sanchit Sir and compare the available GATE course options.