Mathematical-Reasoning · Unit 27 · Video 3 · Interactive Practice

Reading Relation Properties off a Directed Graph

IKey Formulas

Property	On the directed graph	A failure looks like
Reflexive on $A$ : $(x, x) \in R$ for all $x \in A$	a loop at every vertex	one vertex with no loop
Symmetric: $(x, y) \in R \Rightarrow (y, x) \in R$	every arrow has a return arrow (loops are their own reverse)	one arrow with no return
Transitive: $(x, y), (y, z) \in R \Rightarrow (x, z) \in R$	every two-step path $x \to y \to z$ has a shortcut $x \to z$	one two-step path with no shortcut

Key Insight: The path $x \to y \to x$ is a two-step path too, and its shortcut is a loop. So in a transitive relation, arrows in both directions between $x$ and $y$ force loops at $x$ and at $y$ .

IILoops, Return Arrows and Shortcuts

Each property is one feature of the picture; every missing copy of that feature is drawn dashed.

Relation

IIIWalking Every Two-Step Path

Transitivity is a claim about every two-step path, including the paths that go there and back.

Relation Path 1

IVQuiz Questions

Problem 1 · Read All Three

Given: the directed graph of a relation on $\{a, b, c\}$ has a loop at each of $a$ , $b$ , $c$ and the arrows $a \to b$ , $b \to c$ , $a \to c$ , and no other edges. Which properties does the relation have?

✅ Correct! Every vertex has a loop, the arrow

a \to b

has no return, and the only two-step path through different vertices,

a \to b \to c

, has its shortcut

a \to c

❌ Not quite. The arrow

a \to b

has no return arrow

b \to a

, so the relation is not symmetric.

❌ Not quite. Check the shortcuts:

a \to b \to c

has

a \to c

, and every other two-step path uses a loop, whose shortcut is already an edge.

❌ Not quite. None of the three arrows has a return arrow, so the relation is not symmetric.

❌ Not quite. Look for loops, return arrows and shortcuts in turn.

Show solution

Loops: $a$ , $b$ and $c$ all have loops, so the relation is reflexive.

Return arrows: $a \to b$ has no arrow $b \to a$ , so it is not symmetric.

Shortcuts: a two-step path through a loop, such as $a \to a \to b$ , has the shortcut $a \to b$ , which is the other step itself. The only path through three different vertices is $a \to b \to c$ , and $a \to c$ is present. There are no there-and-back paths, since no arrow has a return. So the relation is transitive.

Problem 2 · A Two-Way Pair

Given: on $A = \{1, 2, 3\}$ , the relation $R = \{(1, 1), (1, 2), (2, 1)\}$ . Which single pair, added to $R$ , makes it transitive?

✅ Correct! The path

2 \to 1 \to 2

needs the loop

(2, 2)

. With it,

R = \{(1,1), (1,2), (2,1), (2,2)\}

and every two-step path has its shortcut.

❌ Not quite. Vertex

3

has no arrows, so no two-step path passes through it. Transitivity does not require loops at vertices that sit alone.

❌ Not quite. Adding

(1, 3)

creates nothing

R

needs and leaves the path

2 \to 1 \to 2

without its shortcut.

❌ Not quite.

(2, 1), (1, 2) \in R

but

(2, 2) \notin R

❌ Not quite. Walk the there-and-back paths.

Show solution

The arrows $1 \to 2$ and $2 \to 1$ give two there-and-back paths: $1 \to 2 \to 1$ , whose shortcut $(1, 1)$ is present, and $2 \to 1 \to 2$ , whose shortcut $(2, 2)$ is missing.

Add $(2, 2)$ . The relation $\{(1,1), (1,2), (2,1), (2,2)\}$ contains every pair from $\{1, 2\} \times \{1, 2\}$ , so any two-step path between $1$ and $2$ has its shortcut, and vertex $3$ takes part in no path. The result is transitive (and still not reflexive on $A$ , since $(3, 3)$ is missing).

Problem 3 · Counting Missing Return Arrows

Given: the directed graph of a relation on $\{1, 2, 3, 4\}$ has loops at $1$ and $3$ and the arrows $1 \to 2$ , $2 \to 1$ , $3 \to 4$ , $4 \to 3$ , $2 \to 3$ . What is the fewest number of edges that must be added to make it symmetric?

✅ Correct! Only

2 \to 3

lacks its return; adding

3 \to 2

makes every arrow two-way.

❌ Not quite.

2 \to 3

has no arrow

3 \to 2

❌ Not quite. Symmetry does not ask for loops; the missing loops at

2

and

4

matter for reflexivity, not symmetry.

❌ Not quite. The pairs

1 \leftrightarrow 2

and

3 \leftrightarrow 4

already go both ways; only one arrow is one-way.

❌ Not quite. Count the arrows with no return arrow.

Show solution

Loops are their own reverse, so they never break symmetry. Check each arrow between different vertices:

$1 \to 2$ and $2 \to 1$ : both present.
$3 \to 4$ and $4 \to 3$ : both present.
$2 \to 3$ : the return $3 \to 2$ is missing.

Adding the single edge $3 \to 2$ makes the relation symmetric, and nothing fewer will do.

Problem 4 · When Symmetric and Transitive Force Loops

Given: a relation $R$ on a set $A$ is symmetric and transitive, and every $x \in A$ is related to at least one element of $A$ . Must $R$ be reflexive on $A$ ?

✅ Correct! Each vertex has at least one arrow out; symmetry adds the arrow back, and the there-and-back path forces the loop.

❌ Not quite. The empty relation breaks the extra hypothesis:

1

is related to nothing. That is exactly the case this hypothesis rules out.

❌ Not quite. Here the extra hypothesis supplies an arrow from each vertex, and the there-and-back rule then forces every loop.

❌ Not quite. The conclusion is right but the reason is false:

\{(1, 2), (2, 1)\}

\{1, 2\}

is symmetric and has no loops.

❌ Not quite. Start from an arrow out of

x

and use both properties.

Show solution

Let $x \in A$ . By hypothesis there is some $y \in A$ with $x \mathrel{R} y$ . Since $R$ is symmetric, $y \mathrel{R} x$ . Now $x \mathrel{R} y$ and $y \mathrel{R} x$ , so transitivity (with $z = x$ ) gives $x \mathrel{R} x$ .

Since $x$ was arbitrary, $R$ is reflexive on $A$ . On the graph: every vertex has an arrow out, symmetry supplies the return arrow, and the path $x \to y \to x$ needs the loop at $x$ .

Solved: 0 / 4