maths.free › Combinatorics & Graph Theory › 3. Graph Theory › Relations and Graphs

Relations and Graphs

Investigation Consider the three spinners below. If you and a friend each pick a different spinner and spin them, we can consider the nine possible outcomes.

Section Preview

Investigation

Consider the three spinners below.

If you and a friend each pick a different spinner and spin them, we can consider the nine possible outcomes. For example, between spinners \(A\) and \(B\), the outcomes are \[(2,1), (2,6), (2,8), (4,1), (4,6), (4,8), (9,1), (9,6), (9,8)\]. This suggests that spinner \(A\) will win five out of nine times.

Compare the other combinations of spinners. Which spinner is best?

In this section, we will explore a generalization of a graph, called a relation. We will see how a relation can be represented by a graph and how a graph can be used to represent a relation. We will also consider some properties that a relation might have, and how these properties can be used to classify relations into different types.

Relations Generally

A graph is a way to represent some ways that different objects are related. We have seen how to use graphs to represent which people are friends, or which classes have time conflicts, or which radio stations are too close to have the same frequency. Not all ways in which things can be related can be represented by a graph, however. In this section, we will consider the more general concept of a relation and see how those might be related to graphs.

Consider the example of the relation between students and classes that holds when a student is in that class (in a particular semester). This is a relation between two different sets (the students and the classes). If we used a graph to illustrate this relation, the graph would be bipartite, since two students are never related to each other, and two classes are never related to each other.

A graph is really a set of vertices and a set of edges: \(G = (V, E)\); each element of the set \(E\) is a two-element subset of \(V\). If we want to draw attention to the bipartiteness of the graph, we can split up \(V\) into its two sets and write \(G = ((A, B), E)\). In this notation, for the graph to be bipartite, we want each edge to be a pair \((a,b)\) where \(a\) is an element of \(A\) and \(b\) is an element of \(B\). In other words, each edge is an element of the Cartesian product of \(A\) and \(B\), written, \[A \times B = \{(a,b) \st a \in A,~b \in B\}.\] (Another way to say this is that \(A \times B\) is the set of all ordered pairs of elements from \(A\) and \(B\).)

This example exactly illustrates what a general binary relation is. Here is the careful definition.

Note that \(A \times A\) is just the set of all ordered pairs where both coordinates are elements from \(A\).

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

Properties of Relations

From this point on, we will just consider relations on a single set (so from a set to itself). To help understand these relations, let's consider some basic properties a relation might or might not have.

Let's examine each of these properties carefully.

It will be helpful to consider a few standard examples of relations on sets as we go. Most relations we consider here will be written using infix notation, just meaning that we put the relation symbol between the two things it is relating. For example, the less than relation is almost always written as \(2 \lt 6\) rather than writing \((2,6) \in \lt\).

Example: Reflexive and non-reflexive relations

A relation is reflexive when every element is related to itself. The following are reflexive relations:

The less-than-or-equal-to relation on any set of numbers. Is it the case that \(3 \le 3\)? More importantly, is every number no greater than itself? Since the answer is yes, this relation is reflexive.
The within 3 relation, that holds of two numbers \(a\) and \(b\) provided \(|a-b| \le 3\). To prove that this is reflexive, we simply note that \(|a-a| = 0 \le 3\).
The is a multiple of relation from . Note that the directed multigraph for this relation had loops at every vertex.

However, these relations are not reflexive:

The sums to zero relation, that holds on numbers \(a\) and \(b\) if \(a+b = 0\). Note that while \(0 + 0 = 0\), so \((0,0)\) is an element of the relation, every other number is not related to itself.
Any relation that is described by a graph. Remember, graphs cannot have edges looping back to a single vertex, so the edge relation on a graph is not reflexive. (A multigraph could be reflexive or not).

If no element is related to itself (such as in the edge relation for a graph), then we call the relation irreflexive. Of course, some relations are neither reflexive nor irreflexive.

Checking that a relation is reflexive is relatively easy. The other two properties are phrased as implications, which makes them a little more complex.

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

Equivalence Relations

Now we will do something very typical for mathematics: We will look at our most common types of relations, consider what properties these have, and then classify other relations that also have these properties as a specific class of relations.

The relation we are all most familiar with is equality. Which properties of relations does the equality relation possess? Certainly everything is equal to itself, so equality is reflexive. If \(a = b\), then \(b = a\), so equality is symmetric. If \(a = b\) and \(b = c\), then \(a = c\), so equality is transitive.

What other relations are reflexive, symmetric, and transitive? Exactly those relations that behave like equality. We call such relations equivalence relations.

None of the examples we have considered so far in this section have been equivalence relations, but they are ubiquitous in mathematics. They are so common that it is easy to overlook them as anything worth saying something about at all. Let's see some examples.

Example

Let's call two graphs degree-sequence-equivalent if they have the same degree sequence. Is this an equivalence relation?

Solution

Yes it is. Clearly every graph has the same degree sequence as itself, so the relation is reflexive. If \(G_1\) has the same degree sequence as \(G_2\), then \(G_2\) has the same degree sequence as \(G_1\), so the relation is transitive. Finally, if \(G_1\) has the same degree sequence as \(G_2\), which has the same degree sequence as \(G_3\), then they all have the same degree sequence, so \(G_1\) has the same degree sequence as \(G_3\) (i.e., the relation is transitive).

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

Equivalence Classes and Partitions

Given any relation \(R\), we can look at the set of elements that are related to a particular element. For the is taking relation, we can ask what classes Al is taking (i.e., the classes related to Al). For the is a multiple of, we can ask which numbers 6 a multiple of. One way to study the relation is to study the sets of things related to each element.

Example

Find the relation classes for the is a multiple of relation on the set \(A = \{1,2,3,4,5,6\}\).

Solution

There will be six relation classes since each element has a relation class. They are: \[\begin{aligned}[1] = \amp \{1\} \\ [2] = \amp \{1,2\} \\ [3] = \amp \{1,3\} \\ [4] = \amp \{1,2,4\} \\ [5] = \amp \{1,5\} \\ [6] = \amp \{1,2,3,6\}.\end{aligned}\] For example, we found \([4]\) by considering all pairs \((4,b)\) that satisfied the relation: 4 is a multiple of 1, 2, and 4, so those are the possible values of \(b\) that we find.

Look back at the directed multigraph for this relation shown in the solution to . What are the relation classes? They are nothing but the neighbors of each vertex (where neighbor means you follow the arrows in the correct direction).

Examine the two examples above carefully. For the is a multiple of relation, which is NOT an equivalence relation, some elements belong to more than one (different) relation class. But for \(\equiv_2\), which is an equivalence relation, every element is in exactly one equivalence class. This is no accident. To make sense of this, we will define a new term.

That definition has a lot of symbols and sets involved. It's really not complicated though: A partition is a way to break up a set into disjoint subsets that cover the whole set. That the subsets are disjoint means no element is in more than one subset. That the subsets cover the set means every element is in at least one subset.

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

Practice (18)

Try each one on paper first. Reveal the answer to check; verified ones can be opened in the solver for every step.

Consider the relation \(R\) defined on the integers that holds of \(a\) and \(b\) precisely if \(b-a \ge 4\). So for example, \((2,7) \in R\) but \((8,6) \notin R\). Which of the following properties of relations does \(R\) have?
Not all graphs have a transitive edge relation. But do some of them? If so, give an example and explain why it is transitive. If not, explain why.
After reading this section, what questions do you have? Ask at least one question about this section that you are curious about.
Which of the following relations on the integers are reflexive?
1. \(x \sim y\) if and only if \(x+y\) is odd.
2. \(x \sim y\) if and only if \(x+y\) is positive.
3. \(x \sim y\) if and only if \(xy \ge 0\).
4. \(x \sim y\) if and only if \(xy\) is positive.
5. \(x \sim y\) if and only if \(y-x\) is a multiple of 10.
@ action
1. Not reflexive, since, for example, \(0+0=0\) is not odd.
2. Not reflexive, since, for example, \((-1) + (-1)\) is not positive.
3. Reflexive. Any number times itself is non-negative.
4. Not reflexive. \(0\cdot 0\) is not positive.
5. Reflexive. Since \(n-n = 0\) is a multiple of 10.
Which of the following relations on the integers are symmetric?
1. \(x \sim y\) if and only if \(x+y\) is odd.
2. \(x \sim y\) if and only if \(x+y\) is positive.
3. \(x \sim y\) if and only if \(xy \ge 0\).
4. \(x \sim y\) if and only if \(xy\) is positive.
5. \(x \sim y\) if and only if \(y-x\) is a multiple of 10.
@ action

All the relations listed are symmetric.
Which of the following relations on the integers are transitive?
1. \(x \sim y\) if and only if \(x+y\) is odd.
2. \(x \sim y\) if and only if \(x+y\) is positive.
3. \(x \sim y\) if and only if \(xy \ge 0\).
4. \(x \sim y\) if and only if \(xy\) is positive.
5. \(x \sim y\) if and only if \(y-x\) is a multiple of 10.
@ action
1. Not transitive. For example, \(1 \sim 2\) and \(2 \sim 3\), but \(1 \not\sim 3\).
2. Not transitive. For example, \(-1 \sim 3\) and \(3 \sim -2\), but \(-1 \not\sim -2\).
3. Not transitive. For example, \(-1 \sim 0\) and \(0 \sim 1\), but \(-1 \sim 1\).
4. Transitive. If \(x\sim y\), then \(x\) and \(y\) have the same sign. And then if \(y \sim z\), \(z\) has the same sign as \(y\), so \(z\) also has the same sign as \(x\). Thus \(x \sim z\).
5. Transitive. This is because \(z - y + y - x = z - x\), so if \(z-y\) and \(y-x\) are both multiples of 10, then so is \(z-x\).
Define relations \(R_1,\ldots,R_6\) on \({ 1,2,3,4 }\) by
1. \(R_1=\{ (2,2),(2,3),(2,4),(3,2),(3,3),(3,4) \},\)
2. \(R_2 = \{ (1,1),(1,2),(2,1),(2,2),(3,3),(4,4)\}\).
3. \(R_3 = \{ (2,4),(4,2) \}\).
4. \(R_4 = \{ (1,2),(2,3),(3,4)\}\),
5. \(R_5 = \{ (1,1),(2,2),(3,3),(4,4)\},\)
6. \(R_6=\{ (1,3),(1,4),(2,3),(2,4),(3,1),(3,4) \},\)
For each of the relations, determine whether it is any of reflexive, irreflexive, symmetric, antisymmetric, and transitive.
For each of the following relations on the set of all people, determine whether the relation is any of reflexive, irreflexive, symmetric, anitsymmetric, and transitive.
1. \(a \sim b\) if and only if \(a\) is older than \(b\).
2. \(a \sim b\) if and only if \(a\) and \(b\) have a common grandparent.
3. \(a \sim b\) if and only if \(a\) has the same first name as \(b\).
4. \(a \sim b\) if and only if \(a\) and \(b\) were born on the same day.
For the following relations on the set of all integers, determine whether the relation is any of reflexive, irreflexive, symmetric, antisymmetric, and transitive:
1. \(x \sim y\) if and only if \(x+y = 0\).
2. \(x \sim y\) if and only if \(x - y\) is an integer.
3. \(x \sim y\) if and only if \(x=2y\).
4. \(x \sim y\) if and only if \(xy \gt 1\).
True or false: for any relation \(R\) on a set \(A\), the relation \(R\inv\) is symmetric if and only if \(R\) is symmetric. Justify your answer.
True or false: for any relation \(R\) on a set \(A\), the composition of \(R\) with its inverse, \(R\circ R\inv\), is always reflexive. Justify your answer.
Find, if possible, an example of a relation on the set \(\{1,2,3,4\}\) that is reflexive and symmetric, but not transitive. If such a relation exists, draw the directed multigraph of the relation and list the ordered pairs that define it. Explain your answers.
Find, if possible, an example of a relation on the set \(\{1,2,3,4\}\) that is reflexive and transitive, but not symmetric. If such a relation exists, draw the directed multigraph of the relation and list the ordered pairs that define it. Explain your answers.
Find, if possible, an example of a relation on the set \(\{1,2,3,4\}\) that is symmetric and transitive, but not reflexive. If such a relation exists, draw the directed multigraph of the relation and list the ordered pairs that define it. Explain your answers.
What is wrong with the following argument that any relation that is symmetric and transitive must be reflexive?
Suppose \(R\) is a relation on a set \(A\) that is symmetric and transitive. Since \(R\) is symmetric, if \(aRb\), then \(bRa\) holds. Since \(R\) is transitive, if \(aRb\) and \(bRa\), then \(aRb\) holds. Since this is true for all elements \(a\), we have that \(aRa\) is true for all \(a\) in \(A\), so \(R\) is reflexive.
Suppose \(R\) is an equivalence relation on the set \(A = \{1,2,\ldots,6\}\). What could the directed multigraph for \(R\) look like? Give at least two different examples of such \(R\) and their graphs to illustrate your answer.
Consider the relation \(R\) on the set \(A = \{1,2,3,4,5\}\) defined by \(R = \{(1,2), (2,3), (3,4), (4,5), (5,1), (2,1), (3,1), (4,1), (5,1)\}\). Is \(R\) an equivalence relation? Justify your answer.
Regardless of your answer, what do the relation classes \([a]\) for \(a \in R\) look like? Can you tell whether \(R\) is an equivalence relation from this information?
Consider the loner relation on a set of students that describes friendships, and holds only between a student and themselves (i.e., nobody is friends with anyone other than themselves). Is this an equivalence relation? Justify your answer. If it is an equivalence relation, what do the equivalence classes look like?

Symbols used here

a \equiv b \pmod n

congruent modulo n
n divides a − b; a and b have the same remainder.

x \in A,\ A \subseteq B

element of, subset
x belongs to A; every element of A is in B.

imaginary unit
i² = −1.

\leq,\ \geq

less/greater than or equal
Inequalities that allow equality; < and > exclude it.

factorial
n × (n−1) × … × 1; the number of orderings of n things. 0! = 1.

\binom{n}{k}

binomial coefficient, "n choose k"
Number of k-element subsets of n things: n!/(k!(n−k)!).

\sum_{k=1}^{n} a_k

summation
Add a_k for k = 1 up to n.

\prod_{k=1}^{n} a_k

product
Multiply a_k for k = 1 up to n.

\emptyset,\ |A|

empty set, cardinality
The set with no elements; the number of elements of A.

How to: Relations and Graphs

Explain the relationship between a graph and a relation.
Determine whether a relation is reflexive, symmetric, or transitive.
Use an equivalence relation to partition a set and use a partition to define an equivalence relation.

Questions people ask

Permutation or combination?

Ask whether order matters. A lock code is a permutation (order matters); a hand of cards is a combination (it does not).

What is a graph in this sense?

Dots (vertices) joined by lines (edges) — not a plot. Road maps, social networks and molecules are graphs; questions like "is there a route" and "how few colours" are graph theory.

QDialogButtonBox

Parts of this page are adapted from Levin, Discrete Mathematics: An Open Introduction (CC BY-SA 4.0). Condensed and re-explained here; errors are ours.

@ action Combinatorics & Graph Theory

The counting principles Pigeonhole principle and inclusion–exclusion Binomial coefficients and Pascal's triangle Recurrences and generating functions Graphs: vertices, edges, degrees Paths, cycles, trees, Euler and Hamilton Colouring and planar graphs