# Relations, partial orders and lattices: GATE CS question with solution

From the GATE Daily set of 27 October 2026, question 3 of 10 (https://gatedaily.in/q/2026-10-27-linear-extensions-diamond-poset/). Difficulty: standard.

### Q.3 · Discrete Mathematics · Relations, partial orders and lattices · NAT, 1 mark (answer with a number)

Let $S = \{1, 2, 3, 4, 5\}$ and let $P$ be the partial order on $S$ given by

$$P = \{(x, x) \mid x \in S\} \cup \{(1,2), (1,3), (2,4), (3,4), (1,4), (5,4)\},$$

where $(x, y) \in P$ means $x \preceq y$. A total order on $S$ *contains* $P$ if every pair of $P$ is also a pair of the total order.

The number of total orders on $S$ that contain $P$ is ________.

**Answer:** 8

**Solution.** **Method.** A total order containing $P$ is a way of listing the five elements in a line, smallest first, so that whenever $x \ne y$ and $x \preceq y$ in $P$, $x$ appears before $y$ (a *linear extension*). Read off the structure first:

- $1 \preceq 2$, $1 \preceq 3$, $2 \preceq 4$, $3 \preceq 4$: a diamond with $1$ at the bottom and $4$ at the top.
- $5 \preceq 4$, and $5$ is incomparable with $1, 2, 3$.

Every other element is below $4$, so $4$ must come **last**. Among $\{1, 2, 3\}$, $1$ must come first and $2, 3$ can be in either order: $2$ ways ($1,2,3$ or $1,3,2$). Element $5$ only has to precede $4$, so it can be inserted in any of the $4$ gaps of a 3-element line before $4$ (before $1$, between the first two, between the last two, or right before $4$): $4$ ways.

Total $= 2 \times 4 = 8$.

**The trap.** Two slips are common: ignoring $5$ (answer $2$, the diamond alone) or forgetting it is still bounded by $4$ and letting it go anywhere among 5 positions (answer $10$). Another is to count $5! = 120$ minus "bad" orders, which is error-prone; placing the forced elements first is faster.

**What was tested.** Reading a partial order from its pair list, recognising maximal and minimal elements, and counting linear extensions by fixing forced positions and multiplying independent choices.

**Remember:** To count total orders extending a partial order, place forced elements first (a unique maximum goes last, a unique minimum first), then multiply the independent choices for the rest.