Graded: 10.2 #18, 10.4 #28

9.1 #6

$$\begin{array}{l | c | c | c} & \text{Reflexive?} & \text{Symmetric?} & \text{Antisymm.?} & \text{Transitive?} \\ \hline \text{a)} & \text{No} & \text{Yes} & \text{No} & \text{No} \\ \hline \text{b)} & \text{Yes} & \text{Yes} & \text{No} & \text{Yes} \\ \hline \text{c)} & \text{Yes} & \text{Yes} & \text{No} & \text{Yes} \\ \hline \text{d)} & \text{No} & \text{No} & \text{Yes} & \text{No} \\ \hline \text{e)} & \text{Yes} & \text{Yes} & \text{No} & \text{No} \\ \hline \text{f)} & \text{No} & \text{Yes} & \text{No} & \text{No} \\ \hline \text{g)} & \text{No} & \text{No} & \text{Yes} & \text{Yes} \\ \hline \text{h)} & \text{No} & \text{Yes} & \text{No} & \text{No} \end{array}$$

9.1 #49

The error is in the second sentence. We can’t necessarily take an element $b\in A$ such that $(a,b)\in R$, because there may be no such element.

9.5 #2

a) This is an equivalence relation (the classes are fibers of the function assigning each person his or her age).

b) This is an equivalence relation (the classes are fibers of the function assigning each person his or her set of parents).

c) This is not an equivalence relation as it lacks transitivity. It is possible for person A and person B to share one parent, and for person B and person C to share another parent, while person A and person C do not share a parent.

d) This is not an equivalence relation as it also lacks transitivity. If person A has met person B, and person B has met person C, it does not follow that person A has met person C. (Perhaps this relation also lacks reflexivity? Hard to say if everyone has met him- or herself…)

e) This is not an equivalence relation as it lacks transitivity (for similar reasons to (c) above). It also lacks reflexivity as some people (newborns, for example) do not speak a language.

9.5 #8

Recall that two sets have the same cardinality if and only if there is a bijection between them.

$R$ is reflexive because every set has a bijection to itself, namely the identity map.

$R$ is symmetric because if $f:A\to B$ is a bijection, then $f^{-1}:B\to A$ is also a bijection.

$R$ is transitive because if $f:A\to B$ and $g:B\to C$ are bijections, then $g\circ f:A\to C$ is a bijection.

Thus $R$ is an equivalence relation. The class of $\{0,1,2\}$ is the set of all subsets of $\mathbb R$ having exactly 3 elements. The class of $\mathbb Z$ is the set of all countably infinite subsets of $\mathbb R$.

9.5 #16

Reflexivity: $(a,b)~R~(a,b)$ because $ab=ba$. Thus $R$ is reflexive.

Symmetry: Suppose $(a,b)~R~(c,d)$, that is, $ad=bc$. Then $cb=da$, so $(c,d)~R~(a,b)$. Thus $R$ is symmetric.

Transitivity: Suppose $(a,b)~R~(c,d)$ and $(c,d)~R~(x,y)$. Then $ad=bc$ and $cy=dx$. Multiplying these equations gives $adcy=bcdx$. Since $c,d > 0$, we can divide $cd$ from both sides to get $ay=bx$. Thus $(a,b)~R~(x,y)$. This shows that $R$ is transitive.

9.5 #40

a) The equivalence class consists of all pairs $(a,b)\in\mathbb Z^+\times\mathbb Z^+$ such that $(a,b)~R~(1,2)$, that is, such that $2a=b$. Put another way, the equivalence class consists of all pairs $(a,2a)$ where $a$ is a positive integer.

b) The equivalence class of $(m,n)$ consists of all pairs $(a,b)$ such that $an=mb$, or equivalently such that $\frac ba=\frac nm$. These pairs can be thought of as the integer points on a ray from the origin of slope $\frac nm$.

Alternatively, if we consider $(m,n)$ as corresponding to the fraction $\frac nm$, then equivalent pairs correspond to fractions which are equal in value.

9.5 #62

There are 15 set partitions of $\{1,2,3,4\}$, as follows:

• Into 1 subset: $\{1,2,3,4\}$
• Into 2 subsets: $\{\{1\},\{2,3,4\}\} \quad \{\{2\},\{1,3,4\}\} \quad \{\{3\},\{1,2,4\}\} \quad \{\{4\},\{1,2,3\}\} \quad \{\{1,2\},\{3,4\}\} \quad \{\{1,3\},\{2,4\}\} \quad \{\{1,4\},\{2,3\}\}$
• Into 3 subsets: $\{\{1\},\{2\},\{3,4\}\} \quad \{\{1\},\{3\},\{2,4\}\} \quad \{\{1\},\{4\},\{2,3\}\} \quad \{\{2\},\{3\},\{1,4\}\} \quad \{\{2\},\{4\},\{1,3\}\} \quad \{\{3\},\{4\},\{1,2\}\}$
• Into 4 subsets: $\{\{1\},\{2\},\{3\},\{4\}\}$

Each partition defines an equivalence relation.

Remark. The number of partitions of a set of $n$ elements is the $n^{\text{th}}$ Bell number.

10.1 #28

There’s some room for creativity here. I’d model stations as vertices and use an edge to indicate that two stations are consecutive stops on a subway line, with multiple edges between stations if multiple lines connect those stations. In the case of BART, there is no reason to make the edges directed (since all lines can be ridden in both directions). But some train systems might have directed edges; for example, the trains that move people around airports sometimes go in a clockwise circle, in which the order of the stations cannot be reversed. There are no loops on BART, but a sightseeing train might go in a loop (note that a loop implies getting on and off at the same station with no stops in between).

10.2 #5

No; the sum of degrees must be even.

$\bigstar$ 10.2 #18

Note that it should have been given in the problem that the graph is finite.

Let $G$ be a simple graph with $n\ge 2$ vertices. The possible degrees of a vertex are $0,1,2,\ldots,n-1$. But if there is a vertex of degree $n-1$, then that vertex is adjacent to all others, in which case no vertex can have degree $0$. Thus there are at most $n-1$ distinct degrees among the vertices of $G$. By the pigeonhole principle, some two vertices have the same degree.

10.2 #24

Yes, the graph is bipartite (let $V_1=\{a,b,d,e\}$ and $V_2=\{c,f\}$). In fact, this graph is $K_{2,4}$.

10.2 #26

a) Bipartite only for $n\le 2$, since $K_n$ requires $n$ colors.

b) Bipartite when $n$ is even, as vertices can be colored alternately black and white.

c) Bipartite only for $n=1$, since $W_n$ has a triangle if $n\ge 2$.

d) Bipartite for all $n$. If $V_1$ is the set of vertices labeled by bit strings with an odd number of 1s, and $V_2$ is the set of vertices labeled by bit strings with an even number of 1s, then every edge connects a vertex in $V_1$ to a vertex in $V_2$.

10.2 #60

Each pair of vertices is joined by an edge in exactly one of the graphs $G$ and $\overline G$. Thus the total number of edges in $G$ and $\overline G$ is $\binom n2$, where $n$ is the number of vertices in $G$. Therefore, we have $15+13=\binom n2$, the solution to which is $n=8$.

10.2 #64

Let $G=(V,E)$, where $V=V_1\cup V_2$ and all edges go between $V_1$ and $V_2$. Let $m=|V_1|$ and $n=|V_2|$. Then $m+n=v$. The maximum number of edges is $mn$, or $m(v-m)$. For fixed $v$, the maximum value of $m(v-m)$ is achieved when $m=v/2$, in which case $m(v-m) = v^2/4$. Thus $e\le v^2/4$.

10.3 #28

For an undirected graph, the sum of the entries in the row corresponding to vertex $v$ is the degree of $v$ minus the number of loops at $v$. (Remember, loops contribute 2 to the degree but 1 to the adjacency matrix.)

For a directed graph, the sum of the entries in the row corresponding to vertex $v$ is the out-degree of $v$.

10.3 #38

The graphs are isomorphic, via the following (non-unique) mapping: \begin{align*} u_1 \leftrightarrow v_1 \\ u_2 \leftrightarrow v_3 \\ u_3 \leftrightarrow v_2 \\ u_4 \leftrightarrow v_5 \\ u_5 \leftrightarrow v_4 \end{align*}

10.3 #40

The graphs are not isomorphic, as the second graph has a vertex of degree 4 and the first graph does not.

10.3 #42

The graphs are not isomorphic, as the first graph has two adjacent vertices of degree 4 and the second graph does not.

10.3 #44

The graphs are not isomorphic, as the complement of the first graph is disconnected and the complement of the second graph is connected.

10.4 #21

The graphs are not isomorphic, as the first graph has a cycle of length 3 (a “triangle”) and the second graph does not.

10.4 #24

Two adjacent vertices are on opposite sides of the bipartition, so any path between them must have an odd number of edges.

Let $n$ be odd. The first $n-1$ edges of our path can each be chosen from among 3 options; then there is always one edge that will complete the path. So there are $3^{n-1}$ possible paths when $n$ is odd.

$\bigstar$ 10.4 #28

We argue by induction. The base case is the assertion that a connected graph with 1 vertex has at least 0 edges. This is clearly true.

For the inductive step, let $k\ge 1$ and suppose every connected graph with $k$ vertices has at least $k-1$ edges. We wish to show that every connected graph with $k+1$ vertices has at least $k$ edges. Thus, let $G$ be a connected graph with $k+1$ vertices. If $G$ has at least $k$ edges, we are done. Otherwise, the total degree of all vertices in $G$ is less than $2k$, so some vertex $v_0$ has degree less than $\frac{2k}{k+1}$, hence less than 2. Furthermore, the degree of $v_0$ cannot be 0 (since $G$ is connected and has at least 2 vertices). Thus the degree of $v_0$ is 1.

Let $G’$ be the graph obtained from $G$ by deleting $v_0$ and its attached edge. Then $G’$ has $k$ vertices. By the inductive hypothesis, $G’$ has at least $k-1$ edges. But we deleted an edge from $G$ to get $G’$, so $G$ has at least $k$ edges. This completes the inductive step.

We conclude by mathematical induction that every connected graph on $n$ vertices has at least $n-1$ edges. $\blacksquare$

10.4 #30

Again, it should have been given that the graph is finite!

We argue by contradiction. Let $v_0$ be a vertex of odd degree and suppose there is no path from $v_0$ to another vertex of odd degree. Consider the longest path beginning at $v_0$ that does not repeat an edge. That path must end at a vertex of even degree, $v_1$. If this is the $k^{\text{th}}$ time $v_1$ appears in that path, then $2(k-1)+1$ edges incident to $v_1$ are used in this path. But the degree of $v_1$ is even, so there is some unused edge incident to $v_1$, which means we can extend the path to create a longer path with no repeated edge. That’s a contradiction. We conclude that there must be a path from $v_0$ to another vertex of odd degree. $\blacksquare$

Alternative solution (due to G. Eritsyan; simpler than mine!): Each connected component of a graph has an even number of vertices of odd degree. Thus if any vertex has odd degree, there is another vertex in the same connected component which has odd degree, and (because these vertices are in the same connected component) there is a path joining them. $\blacksquare$