Question

How can the directed graph of a relation \(R\) on a finite set \(A\) be used to determine whether a relation is asymmetric?

Short answer

At most 1 edge between each pair of vertices in the directed graph.

Step-by-step solution

Given data

The directed graph is given.

Concept of asymmetric relation

A relation\(R\)on a set\(A\)is asymmetric if\((b,a) \notin R\)whenever,\((a,b) \in R\).

Determine whether a relation is asymmetric

Let the relation \({\rm{R}}\) be asymmetric.

A loop in the directed graph corresponds to an ordered pair of the form \((a,a)\).

By the definition of asymmetric, the relation \(R\) cannot contains any ordered pairs of the form (a, a) and thus the directed graph cannot contain any loops.

If \((a,b) \in R\), then there is an arrow from point a to point \(b\).

By the definition of asymmetric, if \((a,b) \in R\), then \((b,a) \notin R\).

Thus, it is not possible that there is an arrow from point \(b\) to point \(a\).

Then, it implies that there is at most 1 edge between each pair of vertices in the directed graph.