Let R be a binary relation on A = {a, b, c, d, e, f, g, h} represented by the following two-component digraph. Find the smallest integers m and n such that m < n and R^m = R^n.

GATE 1998 · Discrete Mathematics · Relations · medium

Answer: Smallest m=1, n=3 such that m < n and R^m = R^n.

1. Analyze digraph components and cycle length: From the two-component digraph: one component has a cycle of length 2. The transient (non-cyclic) part enters the cycle after 1 step. Thus the index p = 1 and period k = 2.
2. Compute smallest m < n with R^m = R^n: With index p=1 and period k=2: R^1 = R^3 (since 1 >= p=1 and 3 = 1+2). Smaller candidates: m=0 gives R^0 = identity, R^2 != identity in general. So the smallest m=1, n=3.