Hasse Diagram MCQs: 12 Solved Questions on Greatest, Least, Upper and Lower Bounds

Solve 12 Hasse diagram questions across MCQ, MSQ and NAT formats, with visible cover-pair counts, extremal-element checks, bounds and partition refinement.

KnowledgeGate Team

Exam prep & CS education

Updated 30 Oct 20268 min read
Hasse Diagram MCQs: 12 Solved Questions on Greatest, Least, Upper and Lower Bounds

Hasse diagram questions become difficult when you confuse the order relation with its transitive reduction. A second trap is treating a greatest or least element as if it meant merely maximal or minimal, even though those words use different quantifiers. These 12 solved questions span MCQ, MSQ and NAT formats, with cover-relation counts, LUB and GLB calculations, diagram reading and partition refinement. For bounded, complemented, distributive and Boolean lattice tests, use Lattice and Boolean Algebra MCQs; this set focuses on cover edges, extremal elements, upper and lower bounds, and partition refinement. For the underlying topic, see the Hasse diagram, greatest and least element lesson.

Hasse diagram edges: count covers, not every comparable pair

Join and meet existence, sublattice closure and distributivity are handled in the earlier Lattice MCQs: Join, Meet and Hasse Diagrams; this set applies the cover rule to edge counts and follows it through extremal elements, bounds and partition refinement. In a Hasse diagram, x is joined to y only when x < y and no selected element z satisfies x < z < y. A Hasse diagram omits loops, arrowheads and edges already implied by transitivity.

Question 1, MCQ

GATE 1996 four-cover solution

Let X = {2, 3, 6, 12, 24}. Define a partial order on X by x <= y if x divides y. The number of edges in the Hasse diagram of (X, <=) is

  • (a) 3

  • (b) 4

  • (c) 9

  • (d) None of the above

Answer: (b) 4. The covers are 2 < 6, 3 < 6, 6 < 12 and 12 < 24, so there are four edges. Relations 2 < 12, 2 < 24, 3 < 12, 3 < 24 and 6 < 24 all contain an intermediate selected element and are therefore transitive.

Divisibility Hasse diagram on {2, 3, 6, 12, 24}, with 2 and 3 below 6, then 12 and 24, showing four cover edges and two omitted transitive pairs.

Question 2, NAT

The number of edges in the hasse diagram representation of the partial ordering {(a,b)|a divides b} on {1,2,3,4,6,16,24} is ________

Answer: 8. The covers are 1-2, 1-3, 2-4, 2-6, 3-6, 4-16, 4-24 and 6-24, giving 2 + 2 + 1 + 2 + 1 = 8. Do not add 1-4, 2-16, 2-24 or 3-24, because each has an intermediate divisor in the selected set.

Question 3, NAT

If A = {1, 2, 3, 6, 9, 18} is ordered by divisibility, how many edges does its Hasse diagram have?

Answer: 7. The covers are 1-2, 1-3, 2-6, 3-6, 3-9, 6-18 and 9-18. The chains 1 | 2 | 6 | 18 and 1 | 3 | 9 | 18, together with 3 | 6, remove direct edges such as 1-6, 1-9, 2-18 and 3-18.

Greatest and least versus maximal and minimal elements

A greatest element is above every element, while a least element is below every element. A maximal element only has nothing strictly above it, and a minimal element only has nothing strictly below it. Several maximal elements may exist, but a poset has at most one greatest element.

Question 4, MCQ

UGC NET 2019 greatest-and-least check

Consider the poset ({3, 5, 9, 15, 24, 45}, divisibility). Which statement is correct?

  • (a) There exist a greatest element and a least element

  • (b) There exist a greatest element but not a least element

  • (c) There exist a least element but not a greatest element

  • (d) There does not exist a greatest element and a least element

Answer: (d) There does not exist a greatest element and a least element. A least element would divide all six members, but no member divides both 3 and 5. A greatest element would be a listed common multiple, yet no listed member is divisible by both 24 and 45.

Question 5, NAT

Consider the given lattice:Assume W = no of minimal elements, X = no. of maximal elements, Y= no. of maximum elements and Z= no of minimum elements than W+X+Y+Z = ________

Lattice used to count minimal, maximal, maximum and minimum elements

Answer: 5. The unique bottom node gives W = 1 and Z = 1; the three separate top nodes give X = 3, but none is above the other two, so Y = 0. Therefore W + X + Y + Z = 1 + 3 + 0 + 1 = 5.

Question 6, NAT

Let P = ({1, 2, 3, ..., 20}, divisibility), the poset of integers from 1 to 20 ordered by divisibility. How many maximal elements does it have?

Answer: 10. The maximal elements are {11,12,13,14,15,16,17,18,19,20} because none has a distinct multiple within {1,...,20}. Every number from 1 through 10 does have a larger multiple in the set, including 10 | 20, so none is maximal.

Question 7, MSQ

Choose the correct statements based on the hasse diagram,

Hasse diagram for topological ordering

  • (a) g is the greatest element

  • (b) a is the least element

  • (c) a,b,d,c,e,f,g is a valid topological ordering

  • (d) a,b,c,d,e,f,g is a valid topological ordering

Answer: (b), (c) and (d). Node a lies below every other node, so it is least, while distinct maximal nodes f and g mean g is not greatest. Nodes c and d are incomparable, so either order shown respects every cover direction.

Upper and lower bounds in divisibility posets

For positive integers ordered by divisibility, the GLB of a finite set is its gcd and the LUB is its lcm, provided those values belong to the poset. Do not transfer this shortcut to a different order relation without checking its definition.

Question 8, MCQ

UGC NET 2019 GLB-and-LUB solution

What are the greatest lower bound (GLB) and the least upper bound (LUB) of A = {3, 9, 12} and B = {1, 2, 4, 5, 10}, if they exist in the positive-integer divisibility poset?

  • (a) A: GLB 3, LUB 36; B: GLB 1, LUB 20

  • (b) A: GLB 3, LUB 12; B: GLB 1, LUB 10

  • (c) A: GLB 1, LUB 36; B: GLB 2, LUB 20

  • (d) A: GLB 1, LUB 12; B: GLB 2, LUB 10

Answer: (a). For A, gcd(3,9,12) = 3 and lcm(3,9,12) = 36; for B, gcd(1,2,4,5,10) = 1 and lcm(1,2,4,5,10) = 20. Only option (a) contains all four values.

Question 9, MCQ

Let D36 = {1, 2, 3, 4, 6, 9, 12, 18, 36} with divisibility as the partial order. What is the least upper bound (LUB) of 2 and 3?

  • (a) 12

  • (b) 36

  • (c) 6

  • (d) 18

Answer: (c) 6. The common upper bounds of 2 and 3 within the divisors of 36 are 6, 12, 18 and 36. Since 6 divides all three other candidates, it is the least under divisibility.

Lattice and diagram-bound questions: test existence first

A lattice needs both a join and a meet for every pair. An upper bound of a subset must sit above every member of that subset, not merely some of them.

Question 10, MCQ

UGC NET 2010

A partially ordered set is said to be a lattice if every two elements in the set have:

  • (a) a unique least upper bound

  • (b) a unique greatest lower bound

  • (c) both (A) and (B)

  • (d) none of the above

Answer: (c) both (A) and (B). Every pair must have a unique join, its least upper bound, and a unique meet, its greatest lower bound. Either operation alone is insufficient.

Question 11, NAT

A hasse diagram of a poset given below: Then find the number of upper bounds of the set {a,b,d,e} is ________

Hasse diagram for upper bounds

Answer: 2. Node d is above a, b and e, and reflexivity puts it above itself; h is above d and hence above all four elements. No other node is above the complete set, so the upper-bound set is {d,h} and its count is 2.

Partition refinement: turn containment into a Hasse diagram

For partitions, pi_i P pi_j means every block of pi_i is contained in some block of pi_j. Apply that definition block by block before drawing an edge.

Question 12, MCQ

GATE 2007 partition-refinement diagram

Consider the set S = (A, B, C, D}. Consider the following 4 partitions pi1, pi2, pi3, pi4 on S : pi1 = {ABCD}' , pi2 = {AB}' , {CD}' , pi3 = {ABC}' , {D}' , pi4 = A' , B' , C' , D'. Let P be the partial order on the set of partitions S' = {pi1, pi2, pi3, pi4} defined as follows : pi_i P pi_j if and only if pi_i refines pi_j. The poset diagram for (S', P ) is :

Answer: (c), the diamond. pi4 refines both pi2 and pi3, and both refine pi1; meanwhile pi2 and pi3 are incomparable because {C,D} is not contained in a block of pi3, while {A,B,C} is not contained in a block of pi2. Thus the covers are pi4-pi2, pi4-pi3, pi2-pi1 and pi3-pi1.

Partition-refinement diamond with pi1 at top, pi4 at bottom, pi2 and pi3 in the middle, and a note that the middle partitions are incomparable.

Hasse diagram exam traps: a four-check error table

Trap

Fast check

Questions to retry

Counting every divisibility pair instead of covers

Name an intermediate selected element

Q1-Q3

Treating maximal as greatest

Ask whether it is above every node

Q4-Q7

Swapping gcd and lcm under divisibility

Use GLB = gcd and LUB = lcm

Q8-Q9

Declaring a lattice after checking one pair or bound

Verify both meet and join for every pair

Q10-Q12

For an accuracy routine under a minute, write the relation direction, cross out transitive pairs, circle the top and bottom candidates, then calculate common bounds.

Hasse diagram revision map and next step

Q1-Q3 test edge counting, Q4-Q7 extremal elements, Q8-Q11 bounds, and Q12 order construction. Re-attempt Q2, Q7, Q8 and Q12 without solutions to exercise four distinct reasoning modes.

For the full Discrete Mathematics sequence, use GATE Guidance by Sanchit Sir. For surrounding subjects and practice, browse the GATE preparation category.