# CHAPTER 5: SETS, ETC.

In earlier chapters, we touched on the elements of discrete mathematics. This chapter reviews more completely the notations, definitions, and elementary properties of sets, relations, functions, graphs, and trees. Readers already well versed in this material need only skim this chapter.

# 5.1 Sets

We adopt special notations for frequently encountered sets.

1Some authors start the natural numbers with 1 instead of 0. The modern trend seems to be to start with 0.

Given two sets A and B, we can also define new sets by applying set operations:

`A  B = {x : x  A and x  B} .`

`A  B = {x : x  A and x  B} .`

`A - B = {x : x  A and x  B} .`

Set operations obey the following laws.

`A  A = A,`

`A  A = A.`

`A  B = B  A,`

`A  B = B  A.`

`A  (B  C) = (A  B)  C,`

`A  (B  C) = (A  B)  C.`

`A  (B  C) = (A  B)  (A  C),`

`A  (B  C) = (A  B)  (A  C).`

#### (5.1)

`A  (A  B) = A,`

`A  (A  B) = A.`

`A - (B  C) = (A - B)  (A - C),`

`A - (B  C) = (A - B)  (A - C).`

#### Figure 5.1 A Venn diagram illustrating the first of DeMorgan's laws (5.2). Each of the sets A, B, and C is represented as a circle in the plane.

DeMorgan's laws (5.2) can be rewritten with complements. For any two sets A, B U, we have

their union is S, that is,

In other words, S forms a partition of S if each element of S appears in exactly one Si S.

For any two finite sets A and B, we have the identity

`|A  B| = |A| + |B| - |A  B| ,`

#### (5.3)

from which we can conclude that

`|A  B|  |A| + |B| .`

If A and B are disjoint, then |A B| = 0 and thus |A B| = |A| + |B|. If A B, then |A| |B|.

`A  B = {(a,b) : a  A and b  B}.`

For example, {a, b} {a, b, c} = {(a, a), (a, b), (a, c), (b, a), (b, b), (b, c)}. When A and B are finite sets, the cardinality of their Cartesian product is

`|A  B| = |A|  |B| .`

#### (5.4)

`A1  A2    An = {(a1,a2,...,an):ai  Ai,i = 1, 2,...,n} ,`

whose cardinality is

`|A1  A2    An| = |A1|  |A2|  |An|`

if all sets are finite. We denote an n-fold Cartesian product over a single set A by the set

`An = A  A    A ,`

whose cardinality is |An| = |A|n if A is finite. An n-tuple can also be viewed as a finite sequence of length n (see page 84).

## Exercises

Draw Venn diagrams that illustrate the first of the distributive laws (5.1).

Prove the generalization of DeMorgan's laws to any finite collection of sets:

`|A1  A2    An| =`

`|A1| + |A2| +  + |An|`

`-|A1  A2| - |A1  A3| -      (all pairs)`

`+|A1  A2  A3 +             (all triples)`

`+(-1)n-1 |A1  A2    An| .`

Show that the set of odd natural numbers is countable.

Show that for any finite set S, the power set 2S has 2|S| elements (that is, there are 2|S| distinct subsets of S).

Give an inductive definition for an n-tuple by extending the set-theoretic definition for an ordered pair.

# 5.2 Relations

`a R a`

for all a A. For example, "=" and "" are reflexive relations on N, but "<" is not. The relation R is symmetric if

`a R b implies b R a`

for all a, b A. For example, "=" is symmetric, but "<" and "" are not. The relation R is transitive if

`a R b and b R c imply a R c`

for all a,b,c A. For example, the relations "<," "," and "=" are transitive, but the relation R = {(a, b): a, b N and a = b - 1 } is not, since 3 R 4 and 4 R 5 do not imply 3 R 5.

Proof For the first part of the proof, we must show that the equivalence classes of R are nonempty, pairwise-disjoint sets whose union is A. Because R is reflexive, a [a], and so the equivalence classes are nonempty; moreover, since every element a A belongs to the equivalence class [a], the union of the equivalence classes is A. It remains to show that the equivalence classes are pairwise disjoint, that is, if two equivalence classes [a] and [b] have an element c in common, then they are in fact the same set. Now a R c and b R c, which by symmetry and transitivity imply a R b. Thus, for any arbitrary element x [a], we have x R a implies x R b, and thus [a] [b]. Similarly, [b] [a], and thus [a] = [b].

For the second part of the proof, let A = {Ai} be a partition of A, and define R = {(a,b): there exists i such that a Ai and b Ai}. We claim that R is an equivalence relation on A. Reflexivity holds, since a Ai implies a R a. Symmetry holds, because if a R b, then a and b are in the same set Ai, and hence b R a. If a R b and b R c, then all three elements are in the same set, and thus a R c and transitivity holds. To see that the sets in the partition are the equivalence classes of R, observe that if a Ai, then x [a] implies x Ai, and x Ai implies x [a].

`a R b and b R a imply a = b .`

In a partially ordered set A, there may be no single "maximum" element x such that y R x for all y A. Instead, there may several maximal elements x such that for no y A is it the case that x R y. For example, in a collection of different-sized boxes there may be several maximal boxes that don't fit inside of any other box, yet no single "maximum" box into which any other box will fit.

## Exercises

Prove that the subset relation " on all subsets of Z is a partial order but not a total order.

Give examples of relations that are

a. reflexive and symmetric but not transitive,

b. reflexive and transitive but not symmetric,

c. symmetric and transitive but not reflexive.

Let S be a finite set, and let R be an equivalence relation on S S. Show that if in addition R is antisymmetric, then the equivalence classes of S with respect to R are singletons.

Professor Narcissus claims that if a relation R is symmetric and transitive, then it is also reflexive. He offers the following proof. By symmetry, a R b implies b R a. Transitivity, therefore, implies a R a. Is the professor correct?

# 5.3 Functions

Intuitively, the function f assigns an element of B to each element of A. No element of A is assigned two different elements of B, but the same element of B can be assigned to two different elements of A. For example, the binary relation

`f = {(a,b) : a  N and b = a mod 2 }`

is a function f : N {0,1}, since for each natural number a, there is exactly one value b in {0, 1} such that b = a mod 2. For this example 0 = f (0), 1 = f (1), 0 = f (2), etc. In contrast, the binary relation

`g = {(a,b) : a  N and a + b is even}`

is not a function, since (1, 3) and (1, 5) are both in g, and thus for the choice a = 1, there is not precisely one b such that (a, b) g.

When the domain of a function f is a Cartesian product, we often omit the extra parentheses surrounding the argument of f. For example, if f : A1 A2 An B, we would write b = f (a1, a2, . . . , an) instead of b = f ((a1, a2, . . . , an)). We also call each ai, an argument to the function f , though technically the (single) argument to f is the n-tuple (a1, a2, . . . ,an).

`f(A' = {b  B : b = f(a) for some a  A'} .`

`0    0 ,`

`1    -1 ,`

`2    1 ,`

`3    -2 ,`

`4    2 ,`

`f-1(b) = a if and only if f(a) = b.`

For example, the inverse of the function â(n) = (-1)n n/2 is

## Exercises

Let A and B be finite sets, and let f : A B be a function. Show that

a. if f is injective, then |A| |B|;

b. f f is surjective, then |A| |B|.

Is the function f (x) = x + 1 bijective when the domain and the codomain are N? Is it bijective when the domain and the codomain are Z?

Give a natural definition for the inverse of a binary relation such that if a relation is in fact a bijective function, its relational inverse is its functional inverse.

Give a bijection from Z to Z Z.

# 5.4 Graphs

#### Figure 5.2 Directed and undirected graphs. (a) A directed graph G = (V, E), where V = {1, 2, 3, 4, 5, 6} and E = {(1, 2), (2, 2), (2, 4), (2, 5), (4, 1), (4, 5), (5, 4), (6, 3)}. The edge (2, 2) is a self-loop. (b) An undirected graph G = (V, E), where V = {1, 2, 3, 4, 5, 6} and E = {(1, 2), (1, 5), (2, 5), (3, 6)}. The vertex 4 is isolated. (c) The subgraph of the graph in part (a) induced by the vertex set {1, 2, 3, 6}.

`E' = {(u, v)  E: u, v  V'} .`

#### Figure 5.3 (a) A pair of isomorphic graphs. The vertices of the top graph are mapped to the vertices of the bottom graph by f(1) = u, f(2) = v, f(3) = w, f(4) = x, f(5) = y, f(6) = z. (b) Two graphs that are not isomorphic, since the top graph has a vertex of degree 4 and the bottom graph does not.

The subgraph induced by the vertex set {1, 2, 3, 6} in Figure 5.2(a) appears in Figure 5.2(c) and has the edge set {(1, 2), (2, 2), (6, 3)}.

## Exercises

Show that in an undirected graph, the length of a cycle must be at least 3.

Show that if a directed or undirected graph contains a path between two vertices u and v, then it contains a simple path between u and v. Show that if a directed graph contains a cycle, then it contains a simple cycle.

Show that any connected, undirected graph G = (V, E) satisfies |E| |V| - 1.

Verify that in an undirected graph, the "is reachable from" relation is an equivalence relation on the vertices of the graph. Which of the three properties of an equivalence relation hold in general for the "is reachable from" relation on the vertices of a directed graph?

What is the undirected version of the directed graph in Figure 5.2(a)? What is the directed version of the undirected graph in Figure 5.2(b)?

Show that a hypergraph can be represented by a bipartite graph if we let incidence in the hypergraph correspond to adjacency in the bipartite graph. (Hint: Let one set of vertices in the bipartite graph correspond to vertices of the hypergraph, and let the other set of vertices of the bipartite graph correspond to hyperedges.)

# 5.5 Trees

## 5.5.1 Free trees

The following theorem captures many important facts about free trees.

Let G = (V, E) be an undirected graph. The following statements are equivalent.

1. G is a free tree.

2. Any two vertices in G are connected by a unique simple path.

3. G is connected, but if any edge is removed from E, the resulting graph is disconnected.

4. G is connected, and |E| = |V| - 1.

5. G is acyclic, and |E| = |V| - 1.

6. G is acyclic, but if any edge is added to E, the resulting graph contains a cycle.

Proof (1) (2): Since a tree is connected, any two vertices in G are connected by at least one simple path. Let u and v be vertices that are connected by two distinct simple paths p1 and p2, as shown in Figure 5.5. Let w be the vertex at which the paths first diverge; that is, w is the first vertex on both p1 and p2 whose successor on p1 is x and whose successor on p2 is y, where x y. Let z be the first vertex at which the paths reconverge; that is, z is the first vertex following w on p1 that is also on p2. Let p' be the subpath of p1 from w through x to z, and let p\" be the subpath of p2 from w through y to z. Paths p' and p\" share no vertices except their endpoints. Thus, the path obtained by concatenating p' and the reverse of p\"is a cycle. This is a contradiction. Thus, if G is a tree, there can be at most one path between two vertices.

#### Figure 5.5 A step in the proof of Theorem 5.2: if (1) G is a free tree, then (2) any two vertices in G are connected by a unique simple path. Assume for the sake of contradiction that vertices u and v are connected by two distinct simple paths p1 and p2. These paths first diverge at vertex w, and they first reconverge at vertex z. The path p' concatenated with the reverse of the path p\" forms a cycle, which yields the contradiction.

(2) (3): If any two vertices in G are connected by a unique simple path, then G is connected. Let (u, v) be any edge in E. This edge is a path from u to v, and so it must be the unique path from u to v. If we remove (u, v) from G, there is no path from u to v, and hence its removal disconnects G.

(3) (4): By assumption, the graph G is connected, and by Exercise 5.4-4, we have |E| |V| - 1. We shall prove |E| |V| - 1 by induction. A connected graph with n = 1 or n = 2 vertices has n - 1 edges. Suppose that G has n 3 vertices and that all graphs satisfying (3) with fewer than n vertices also satisfy |E| |V| - 1. Removing an arbitrary edge from G separates the graph into k 2 connected components (actually k = 2). Each component satisfies (3), or else G would not satisfy (3). Thus, by induction, the number of edges in all components combined is at most |V| - k |V| - 2. Adding in the removed edge yields |E| |V| - 1.

(4) (5): Suppose that G is connected and that |E| = |V| - 1. We must show that G is acyclic. Suppose that G has a cycle containing k vertices v1, v2, . . . , vk. Let Gk = (Vk, Ek) be the subgraph of G consisting of the cycle. Note that |Vk| = |Ek| = k. If k < |V|, there must be a vertex vk+1 V - Vk that is adjacent to some vertex vi Vk, since G is connected. Define Gk+1 = (Vk+1, Ek+1) to be the subgraph of G with Vk+1 = Vk{vk+1} and Ek+1 = Ek{(v1, vk+1)}. Note that |Vk+1| = |Ek+1| = k+1. If k+1 < n, we can continue, defining Gk+2 in the same manner, and so forth, until we obtain Gn = (Vn, En), where n = |V|, Vn = V, and |En| = |Vn| = |V|. Since Gn is a subgraph of G, we have En E, and hence |E| |V|, which contradicts the assumption that |E| = |V| - 1. Thus, G is acyclic.

(5) (6): Suppose that G is acyclic and that |E | = |V | - 1. Let k be the number of connected components of G. Each connected component is a free tree by definition, and since (1) implies (5), the sum of all edges in all connected components of G is |V | - k. Consequently, we must have k = 1, and G is in fact a tree. Since (1) implies (2), any two vertices in G are connected by a unique simple path. Thus, adding any edge to G creates a cycle.

(6) (1): Suppose that G is acyclic but that if any edge is added to E, a cycle is created. We must show that G is connected. Let u and v be arbitrary vertices in G. If u and v are not already adjacent, adding the edge (u, v) creates a cycle in which all edges but (u, v) belong to G. Thus, there is a path from u to v, and since u and v were chosen arbitrarily, G is connected.

## 5.5.2 Rooted and ordered trees

2The term "node" is often used in the graph theory literature as a synonym for "vertex." We shall reserve the term "node" to mean a vertex of a rooted tree.

#### Figure 5.6 Rooted and ordered trees. (a) A rooted tree with height 4. The tree is drawn in a standard way: the root (node 7) is at the top, its children (nodes with depth 1 ) are beneath it, their children (nodes with depth 2) are beneath them, and so forth. If the tree is ordered, the relative left-to-right order of the children of a node matters; otherwise it doesn't. (b) Another rooted tree. As a rooted tree, it is identical to the tree in (a), but as an ordered tree it is different, since the children of node 3 appear in a different order.

3Notice that the degree of a node depends on whether T is considered to be a rooted tree or a free tree. The degree of a vertex in a free tree is, as in any undirected graph, the number of adjacent vertices. In a rooted tree, however, the degree is the number of children--the parent of a node does not count toward its degree.

## 5.5.3 Binary and positional trees

contains no nodes, or

The binary tree that contains no nodes is called the empty tree or null tree, sometimes denoted NIL. If the left subtree is nonempty, its root is called the left child of the root of the entire tree. Likewise, the root of a nonnull right subtree is the right child of the root of the entire tree. If a subtree is the null tree NIL, we say that the child is absent or missing. Figure 5.7(a) shows a binary tree.

#### Figure 5.7 Binary trees. (a) A binary tree drawn in a standard way. The left child of a node is drawn beneath the node and to the left. The right child is drawn beneath and to the right. (b) A binary tree different from the one in (a). In (a), the left child of node 7 is 5 and the right child is absent. In (b), the left child of node 7 is absent and the right child is 5. As ordered trees, these trees are the same, but as binary trees, they are distinct. (c) The binary tree in (a) represented by the internal nodes of a full binary tree: an ordered tree in which each internal node has degree 2. The leaves in the tree are shown as squares.

by equation (3.3). Thus, a complete binary tree has 2h - 1 internal nodes.

## Exercises

Draw all the free trees composed of the 3 vertices A, B, and C. Draw all the rooted trees with nodes A, B, and C with A as the root. Draw all the ordered trees with nodes A, B, and C with A as the root. Draw all the binary trees with nodes A, B, and C with A as the root.

Show that for n 7, there exists a free tree on n nodes such that picking each of the n nodes as a root results in a different rooted tree.

Let G = (V, E) be a directed acyclic graph in which there is a vertex v0 V such that there exists a unique path from v0 to every vertex v V. Prove that the undirected version of G forms a tree.

Show by induction that the number of degree-2 nodes in any binary tree is 1 less than the number of leaves.

Show by induction that a binary tree with n nodes has height at least lg n.

Show that every binary tree with L leaves contains a subtree having between L/3 and 2L/3 leaves, inclusive.

# Problems

a. Show that any tree is 2-colorable.

b. Show that the following are equivalent:

1. G is bipartite.

2. G is 2-colorable.

3. G has no cycles of odd length.

c. Let d be the maximum degree of any vertex in a graph G. Prove that G can be colored with d + 1 colors.

d. Show that if G has O(|V|) edges, then G can be colored with O colors.

Reword each of the following statements as a theorem about undirected graphs, and then prove it. Assume that friendship is symmetric but not reflexive.

a. In any group of n 2 people, there are two people with the same number of friends in the group.

b. Every group of six people contains either three mutual friends or three mutual strangers.

c. Any group of people can be partitioned into two subgroups such that at least half the friends of each person belong to the subgroup of which that person is not a member.

d. If everyone in a group is the friend of at least half the people in the group, then the group can be seated around a table in such a way that everyone is seated between two friends.

a. Show that by removing a single edge, we can partition the vertices of any n-vertex binary tree into two sets A and B such that |A| 3n/4 and |B| 3n/4.

b. Show that the constant 3/4 in part (a) is optimal in the worst case by giving an example of a simple tree whose most evenly balanced partition upon removal of a single edge has |A| = 3n/4.

c. Show that by removing at most O(lg n) edges, we can partition the vertices of any n-vertex tree into two sets A and B such that |A| = n/2 and |B| = n/2.

# Chapter notes

G. Boole pioneered the development of symbolic logic, and he introduced many of the basic set notations in a book published in 1854. Modern set theory was created by G. Cantor during the period 1874-1895. Cantor focused primarily on sets of infinite cardinality. The term "function" is attributed to G. W. Leibnitz, who used it to refer to several kinds of mathematical formulas. His limited definition has been generalized many times. Graph theory originated in 1736, when L. Euler proved that it was impossible to cross each of the seven bridges in the city of Königsberg exactly once and return to the starting point.

A useful compendium of many definitions and results from graph theory is the book by Harary [94].