Appendix B

Exercise B.1-1

Proving the first of the distributive laws with Venn diagrams.

Exercise B.1-2

We prove the statement using induction on n.

Proving the generalization of the first of DeMorgan’s laws

The base case $n=2$ trivially holds. For $n>2$ we have

$$\begin{align*} \overline{A_1\cap A_2\cap\dots\cap A_{n-1}\cap A_n} &= \overline{(A_1\cap A_2\cap\dots\cap A_{n-1})\cap A_n} && \text{(associativity)} \\ &= \overline{A_1\cap A_2\cap\dots\cap A_{n-1}}\cup\overline{A_n} && \text{(by the base case)} \\ &= \overline{A_1}\cup\overline{A_2}\cup\dots\cup\overline{A_{n-1}}\cup\overline{A_n} && \text{(by the inductive hypothesis)} \end{align*}$$

Using the principles of mathematical induction we can conclude that the first of DeMorgan’s laws is applicable to any finite collection of sets.

Proving the generalization of the second of DeMorgan’s laws

The proof is analogous to the previous case, just swap the symbols $\cap$ and $\cup$.

Exercise B.1-3

We prove the statement using induction on n. The base case $n=2$ trivially holds. For $n>2$ we have

$$\begin{align} \notag |A_1\cup A_2\cup\dots\cup A_n| &= |(A_1\cup A_2\cup\dots\cup A_{n-1})\cup A_n| && \text{(associativity)} \\ \notag &= |A_1\cup A_2\cup\dots\cup A_{n-1}|+|A_n| \\ \notag &\qquad {}-|(A_1\cup A_2\cup\dots\cup A_{n-1})\cap A_n| && \text{(by the base case)} \\ &= |A_1\cup A_2\cup\dots\cup A_{n-1}|+|A_n| \\ &\qquad {}-|(A_1\cap A_n)\cup\dots\cup(A_{n-1}\cap A_n)| && \text{(generalized distributive law)} \end{align}$$

The proof for the generalization of distributive laws to any finite collection of sets follows the template laid out in Exercise B.1-2.

We now apply the inductive hypothesis on subexpressions in (1) and (2).

$$\begin{gather*} \begin{align*} |A_1\cup A_2\cup\dots\cup A_{n-1}| &= \sum_{1\le i<n}|A_{i}| \\ &\qquad {}-\sum_{1\le i<j<n}|A_{i}\cap A_{j}| \\ &\qquad {}+\sum_{1\le i<j<k<n}|A_{i}\cap A_{j}\cap A_{k}| \\[-2mm] &\hspace{4cm}\vdots \\ &\qquad {}+(-1)^{n-2}\,|A_1\cap A_2\cap\dots\cap A_{n-1}|, \end{align*}\\[5mm] \begin{align*} |(A_1\cap A_n)\cup\dots\cup(A_{n-1}\cap A_n)| &= \sum_{1\le i<n}|A_{i}\cap A_n| \\ &\qquad {}-\sum_{1\le i<j<n}|A_{i}\cap A_{j}\cap A_n| \\[-2mm] &\hspace{3cm}\vdots \\ &\qquad {}+(-1)^{n-2}\,|A_1\cap A_2\cap\dots\cap A_{n-1}\cap A_n| \end{align*} \end{gather*}$$

Observe that every term in the expansion of the subexpression (2) is initially prefixed with a negative sign. Therefore, each term must be multiplied by -1 when reinserted into the main formula. Ultimately, we have

$$\begin{align*} |A_1\cup A_2\cup\dots\cup A_n| &= \sum_{1\le i\le n}|A_{i}| \\ &\qquad {}-\sum_{1\le i<j\le n}|A_{i}\cap A_{j}| \\ &\qquad {}+\sum_{1\le i<j<k\le n}|A_{i}\cap A_{j}\cap A_{k}| \\[-2mm] &\hspace{3.5cm}\vdots \\ &\qquad {}+(-1)^{n-1}\,|A_1\cap A_2\cap\dots\cap A_n| \end{align*}$$

Using the principles of mathematical induction we can conclude that the generalized variant of equation (B.3) holds for all $n \ge2$.

Exercise B.1-4

The function $f(n)=2n+1$ maps a natural number (with zero included) to it's odd counterpart. This establishes a bijection between natural numbers and odd natural numbers. Therefore, the set of odd natural numbers is countable.

Exercise B.1-5

Let $S=\{e_0, e_1,..., e_{n−1}\}$ and $n=|S|$. In a power set, each element either joins a subset or not. Suppose participation is denoted by 1 and absence by 0. Represent any subset $S'$ as an n-digit binary number $b_{n-1}b_{n-2}...b_0$, where $b_i=1 \implies e_i \in S'$. This creates a bijection between n-digit binary numbers and subsets of a power set. With n binary digits, there are $2^n$ possible values. This shows that for any finite set S, the power set $2^S$ has $2^{|S|}$ elements.

Observe that the previous proof also answers the question how to non-recursively generate all subsets of a power set. Just iterate over all integers in $[0,2^n)$, convert them into binary, and produce subsets based upon those binary representations as described above.

Exercise B.1-6

$$(a_1,a_2,\dots,a_n) = \begin{cases} \emptyset & \text{if $n=0$},\\ \{a_1\} & \text{if $n=1$}, \\ \{a_1,\{a_1,a_2\}\} & \text{if $n=2$} ,\\ (a_1,(a_2,\dots,a_n)) & \text{if $n\ge3$}. \end{cases}$$

Exercise B.2-1

The subset relation $\subseteq$ is reflexive, antisymmetric and transitive as explained in the book. Consequently, it represents a partial order on all subsets of ℤ. It is not a total order, since there are many pairs of subsets that are not in relation with each other. For example, {0,1} and {1,2,3}.

Exercise B.2-2

We need to show that the relation "equivalent modulo n" is reflexive, symmetric and transitive.

• $a−a=0n \implies a=a \text{ (mod n)} \qquad \checkmark$

• $a=b \text{ (mod n)} \implies a−b=qn \implies b-a=(-q)n \implies b=a\text{ (mod n)} \qquad \checkmark$

• $(a=b\text{ (mod n)} \land b=c\text{ (mod n)})\implies ((a−b=q_1n)\land (b-c=q_2n))$. Therefore, $a−c=a−b+b−c=q_1 n+q_2 n=(q_1+q_2 )n \implies a=c\text{ (mod n)} \qquad \checkmark$

The relation “equivalent modulo n” splits the integers into congruency classes. Two integers are regarded equivalent if they have the same remainder when divided by n.

Exercise B.2-3

1. $R=\{(a,b):a,b\in\N \land |a-b|\le1\}$ is not transitive, since 3 $R$ 4 and 4 $R$ 5 do not imply 3 $R$ 5.

2. $R=\{(a,b):\text{b is reachable from a in a directed acyclic graph}\}$ is not symmetric otherwise there would be a cycle.

3. Let $S=\{1,2,3\}$. $R=\{(1,2),(2,1),(1,1),(2,2)\}$ as a relation on $S \times S$ is not reflexive, since $(3,3)$ is missing. As a matter of fact, even an empty relation on $S \times S$ would still be symmetric and transitive, but not reflexive (see the explanation in Exercise B.2-5).

Exercise B.2-4

Suppose some equivalence class has at least two distinct elements $a$ and $b$. Since $R$ is symmetric, $a\,R\,b \implies b\,R\,a$. But this contradicts $R$'s antisymmetry, $(a\,R\,b \land b\,R\,a) \implies a=b$. Therefore, all equivalence classes of $S$ with respect to $R$ must be singletons.

Exercise B.2-5

Professor Narcissus is wrong, as Exercise B.2-3 demonstrates.

Symmetry and transitivity are defined through implications. The fallacy stems from presuming that an antecedent must be true for an implication $p\implies q$ to be true, as well. But if there is an element that is not related to any other element, including itself, then it does not break symmetry or transitivity. On the other hand, reflexivity demands that all elements be related with themselves.

Exercise B.3-1

1. If $f$ is injective, then each element of $A$ is mapped to a unique element in $B$. Therefore, there must be at least as many elements in $B$ as there are in $A$. Thus, $|A|\le|B|$.

2. If $f$ is surjective, then every element in $B$ has some element from $A$ mapped into it. So, there are at least as many elements in $A$ as there are in $B$. This conclusion also relies on $f$ being a function, meaning that no single argument is mapped to multiple values. Thus, $|A|\ge|B|$.

Exercise B.3-2

If the domain and codomain are natural numbers, the function is not a bijection because zero is not in the range. However, if we include all integers, it becomes a bijection.

Exercise B.3-3

Let $R$ be a binary relation on sets $A$ and $B$. We define its inverse $R^{-1}$ as

$b\,R^{-1}\,a \iff a\,R\,b$ .

Observe that if $R$ is in fact a bijective function, then its relational inverse is its functional inverse. This follows from the definition of an inverse function (see the book).

Exercise B.3-4

A pairing function is a function that reversibly maps $\N \times\N$ onto $\N$. We cannot use it directly, as we need to work with set $\Z$. So, we will perform a composition of bijective transformations.

Bijection from $\Z$ to $\N$

Use the function $f^{-1}:\Z \mapsto \N$ from the book (see page 1163).

Bijection from $\N$ to $\N \times\N$

We can use the inverse of the Cantor's pairing function (see (8) in the above linked material) $g^{-1}:\N \mapsto\N \times\N$ to produce matching pairs from natural numbers.

Bijection from $\N$ to $\Z$

Use the function $f:\N \mapsto \Z$ from the book (see page 1162).

Composition of transformations

We are now ready to connect all the individual components into a pipeline. Define the bijective function $h: \Z \mapsto \Z \times \Z$ as

$$h(n)=(f(a),f(b)), \text{where } (a,b)=g^{-1}(f^{-1}(n)).$$

The presented tactic works because a composition of bijections is a bijection (you can read the proof in the attached PDF file. It was retrieved on July, 2025 from here).

165KB

What Makes a Good Proof.pdf

PDF

Open

Exercise B.4-1

We prove the handshaking lemma by induction on $|E|$. The base case $|E|=0$ obviously holds. For the inductive step, assume that $|E|>0$ and pick any edge $e \in E$. Let $G'=(V,E')$ be the subgraph of $G$ where $E'=E-\{e\}$. The total count becomes

$$\begin{align*} \sum_{v \in V} degree(v)&=\sum_{v \in V} degree'(v) \\ &\qquad+ 2 && \text{(contribution of the removed edge)} \\ &=2(|E|-1)+2 && \text{(by the inductive hypothesis for G')} \\ &=2|E|. \end{align*}$$

The $degree'(v)$ denotes the degree of a node $v$ in $G'$. By the principles of mathematical induction we can conclude that the handshaking lemma is true for any undirected graph $G$.

The original problem can be reformulated in terms of an undirected graph, where vertices are professors and edges represent handshakings between them.

Exercise B.4-2

Let $p=\braket{u=v_0,v_1,...,v_n=v}$ denote a valid path/cycle.

The iterative path simplifying function is depicted below:

1. If $v_0=v_n$, then return $\empty$. There is always a 0-length path from $v_0$ to itself.

2. If $p$ is a simple path, then return $p$.

3. Find indices $(i,j)$, $i<j$, of a repeated vertex $v$ and drop the subpath $\braket{v_i,v_{i+1},...,v_{j-1}}$ from $p$. If $i=0$, then $p$ still starts at $v_j=v_0$, but with one less repetition of $v_0$, so it is a valid path. Otherwise, $p=\braket{v_0,v_1,...,v_{i-1},v_j,...,v_n}$, which is again a valid path; we know that there is an edge $(v_{i-1},v_j)$, because the previous path had a subpath $\braket{v_{i-1},v_i}$ and $v_i=v_j$.

4. Repeat steps 2-3.

Observe that the procedure will terminate, as each iteration reduces the number of duplicates in $p$. Also, it is correct, because step 3 is proven to produce a new valid path and steps 2-3 execute until no duplicates are found.

We can reuse our path simplifier function for a cycle as follows:

1. Let $p'$ be the result of simplifying the path $p$ without the initial vertex $v_0$.

2. If $p'=\empty \implies p'=\braket{v_n}$

3. Output $\braket{v_0} \Join p'$.

It is important to emphasize that both procedures only promise to emit a simple path/cycle at exit. This is enough to prove that any path/cycle contains a simple path/cycle. Starting from $p=\braket{a,b,c,d,e,e,b,e,e,f}$ both $p'=\braket{a,b,e,f}$ and $p''=\braket{a,b,c,d,e,f}$ are possible outputs depending on the order of removal of duplicated vertices. But satisfying such additional quality attributes. like minimizing the path/cycle length, are out of scope of this exercise.

Exercise B.4-3

We prove $|E|\ge|V|-1$ by induction on $|V|$. The base case $|V|=1$ clearly hold.

For the inductive step, assume that $|V|\ge2$ for graph $G$ and pick a vertex $v \in V$. Let $G'=(V',E')$ be the subgraph of $G$ induced by $V'=V-\{v\}$. We have that $|V'|=|V|-1 \land |E'|<|E|$, as connectedness of $G$ entails that there is at least one edge incident on $v$. $G'$ may have $1 \le k \le |V'|$ connected components. Consider each connected component as a subgraph $G'_i=(V'_i,E'_i)$ for which the inductive hypothesis applies, hence $|E'_i|\ge|V'_i|-1$. Consequently, the number of edges in all connected components of $G'$ is at least $|V'|-k$. Furthermore, we know that $|E| \ge |E'| + k$ because $G$ is connected, so all $k$ components of $G'$ must have been connected through vertex $v$. Reconnecting them (including $v$ itself) requires at least $k$ additional edges. As a side note, if $k=1$, then we need at least one edge to reconnect $v$.

Therefore, the total number of edges satisfies

$$\begin{align*} |E| &\ge |E'|+k \\ &\ge (|V'|-k)+k && \text{(by the inductive hypothesis applied for G')} \\ &=|V|-1 \end{align*}$$

According to the principles of mathematical induction we can conclude that any connected, undirected graph $G=(V,E)$ satisfies $|E|\ge|V|-1$.

Exercise B.4-4

We need to show that in an undirected graph, the "is reachable from" relation is reflexive, symmetric and transitive.

• Any vertex is reachable from itself via a 0-length path. $\checkmark$

• If there is a path $u\overset{p}{\leadsto}v$, then due to bidirectional edges there is also a path $v\overset{p'}{\leadsto}u$, where $p'$ is $p$ reversed. $\checkmark$

• If there are paths $u\overset{p_1}{\leadsto}v \land v\overset{p_2}{\leadsto}w$, then there is also a path $u\overset{p_1 \Join p_2}{\leadsto}w$ via vertex $v$. $\checkmark$

In a directed graph, symmetry does not hold in general, since edges cannot be reused for "moving" in both directions. The other two properties do hold.

Exercise B.4-5

Left: the undirected version of the directed graph in Figure B.2(a) Right: the directed version of the undirected graph in Figure B.2(b)

Exercise B.4-6

Wikipedia has published a solution aligned with the hint from the book.

Exercise B.5-1

(a) All the free trees composed of the three vertices x, y, and z. (b) All the rooted trees with nodes x, y, and z with x as the root. (c) All the ordered trees with nodes x, y, and z with x as the root. (d) All the binary trees with nodes x, y, and z with x as the root.

Exercise B.5-2

Observe that an undirected version of graph $G$ is connected. There is a path from vertex $v_0$ to every other vertex in both directions. Hence, any two vertices are connected via this central vertex $v_0$.

The in-degree of every vertex except $v_0$ in graph $G$ is 1. Assume, for contradiction, that there is a vertex $v \in V \land v_0 \neq v$ whose in-degree is larger than 1. WLOG let it be 2. Consequently, there are two neighbors $u$ and $w$ connected to $v$ with edges $(u,v)$ and $(w,v)$ making two different paths $v_0 \leadsto u \to v$ and $v_0 \leadsto w \to v$ toward $v$. But this is impossible, since graph $G$ has unique paths from $v_0$ to every other vertex.

Vertex $v_0$ has in-degree of zero, otherwise there would be a cycle in $G$. Therefore, each vertex except $v_0$ is associated with one incoming edge, so $|E|=|V|-1$. According to Theorem B.2 a connected graph with this number of edges is a free tree.

Exercise B.5-3

We proceed by induction on $|V|$. The base case is when $|V|=1$, which is a binary tree with one leaf without a degree-2 node. Hence, the base case is true.

For the inductive step, assume $|V|>1$. Denote by $L$ and $D$ the number of leaves and degree-2 nodes in a binary tree, respectively. If we take out the root node, then we obtain two subtrees. If anyone of them is empty, then the statement follows by applying the inductive hypothesis on the other nonempty subtree, as the root is neither a leaf nor degree-2 node in this case. Otherwise, denote by $L_L$ and $D_L$ the number of leaves and degree-2 nodes in the left subtree, respectively. Similarly, let $L_R$ and $D_R$ be the same for the right subtree. We have $L=L_L+L_R$ and we can apply the inductive hypothesis on both subtrees to get

$$\begin{align*} D&=D_L+D_R+1 && \text{(the root is now a degree-2 node)} \\ D&=L_L-1+L_R-1+1 && \text{(by the inductive hypothesis) }\\ D&=L-1 \end{align*}$$

In a full binary tree, all internal nodes are degree-2 nodes, so the conclusion from the book follows.

Exercise B.5-4

Execute the following iterative function to create a full binary tree with $k \ge 1$ leaves:

1. Let $T$ be a single node binary tree. It is a full binary tree with no degree-2 node.

2. Repeat steps a-b $k-1$ times:

   1. Create a new binary tree $T'$ with a degree-2 root node whose left child is $T$ and the right child is a leaf node. $T'$ is a full binary tree with one more leaf than $T$.

   2. Let $T=T'$.

3. Return $T$.

The previous proof method is called constructive proof.

Exercise B.5-5

We proceed by induction on $n$. The base case $n=1$ clearly holds, since $h=0 \ge \lfloor \lg 1\rfloor=0$.

For the inductive step, assume the statement holds for all nonempty binary trees with less than $n$ nodes. Consider a binary tree with $n>1$. If one child is empty, then

$$\begin{align*} h &\ge 1 + \lfloor \lg (n-1) \rfloor && \text{(by the inductive hypothesis)} \\ &= \lfloor 1 + \lg (n-1) \rfloor \\ &= \lfloor \lg 2(n-1) \rfloor \\ &\ge \lfloor \lg n \rfloor && \text{(for } n \ge 2\text{)} \end{align*}$$

Suppose that both children are nonempty. Let $n_L$ and $n_R$ be the number of nodes in the left and right subtree, respectively. By the inductive hypothesis we have $h_L \ge \lfloor \lg n_L \rfloor$ and $h_R \ge \lfloor \lg n_R \rfloor$, hence $n_L \le 2^{h_L+1}-1$ and $n_R \le 2^{h_R+1}-1$. The last conclusion follows from observations that $\lfloor \lg (2^{k+1}-1) \rfloor = k$ for any integer $k \ge 0$ as well as that both $\lg x$ and $\lfloor x \rfloor$ are monotonically increasing functions. As a matter of fact, $\lfloor \lg x \rfloor$ returns $k$ for all $x \in [2^k,2^{k+1})$.

We have

$$\begin{align*} n&=n_L+n_R+1 \\ &\le 2^{h_L+1}-1 + 2^{h_R+1}-1 + 1 \\ &\le 2^h+2^h-1 \\ &= 2^{h+1}-1 \\ &\therefore h \ge \lfloor \lg n \rfloor \end{align*}$$

According to the principles of mathematical induction we can conclude that the statement from the book is true for all nonempty binary trees.

Exercise B.5-6

We proceed by induction on $n$. The base case $n=0$ trivially holds, as the only full binary tree with no internal node has one leaf at depth 0.

For the inductive step, take $n >0$ and assume the statement is true for all full binary trees with less than $n$ internal nodes. Take out the root of a full binary tree with $n$ internal nodes. Let $n_L$ and $n_R$ denote the number of internal nodes in its left and right subtree, respectively. We have that $n=n_L+n_R+1$ and we know that both subtrees are also full binary trees. According to Exercise B.5-3 the number of leaves in a full binary tree is one more than its number of internal nodes. Furthermore, the root contributes +1 to the depth of all other nodes. After combining these facts we have

$$i=(i_L+n_L)+(i_R+n_R)=(i_L+n_L)+(i_R+n-n_L-1)=n+i_L+i_R-1$$

and

$$e=(e_L+n_L+1)+(e_R+n_R+1)=(e_L+n_L+1)+(e_R+n-n_L)=n+e_L+e_R+1$$

We can now apply the inductive hypothesis to both subtrees to get

$$\begin{align*} e-i&=n+e_L+e_R+1-n-i_L-i_R+1 \\ &=i_L+2n_L+i_R+2n_R-i_L-i_R+2 && \text{(by the inductive hypothesis)} \\ &=2(n_L+n_R+1) \\ &=2n \\ &\therefore e=i+2n \end{align*}$$

According to the principles of mathematical induction we can conclude that the statement from the book is true for all full binary trees.

Exercise B.5-7

We proceed by induction on number of nodes $n$. The base cases are when $n=0 \lor n=1$ (they both hold)

$$\begin{align*} n=0 &\implies \sum_{x \in \empty} {w(x)}=0\\ n=1 &\implies \sum_{x \in L} {w(x)}=2^0=1 \end{align*}$$

For the inductive step, take $n>1$ and assume it holds for all binary tree with less than $n$ nodes. Take out the root of a binary tree with $n$ nodes. Let $L_L$ and $L_R$ denote the set of leaves in its left and right subtree, respectively. Notice that the root contributes +1 to the depth of all leaves. After combining these facts we have

$$\begin{align*} \sum_{x \in L} {w(x)}&=\frac {1}{2}\big(\sum_{x \in L_L} {w(x)}+\sum_{x \in L_R} {w(x)}\big) \\ &\le \frac {1}{2}(1+1) && \text{(by the inductive hypothesis)} \\ &=1 \end{align*}$$

According to the principles of mathematical induction we can conclude that the Kraft inequality is true for all binary trees.

The Kraft-McMillan inequality has a very important role in coding theory; gives a necessary and sufficient condition for the existence of a prefix code over a given alphabet.

Exercise B.5-8

We proceed using the constructive proof method. The algorithm below outputs a subtree matching the constraints from the problem description.

1. Let the current node become the root of a binary tree with $L \ge 2$ leaves.

2. Take the children of the current node.

3. Choose the larger child based on number of leaves and let the current node become its root.

4. If it has more than $\frac {2}{3}L$ leaves, then goto step 2.

5. Output this subtree.

The algorithm will terminate, since in each iteration the larger subtree has at least one node less than a tree from the previous iteration (its root surely disappears).

It correctly outputs the matching subtree. Notice that the loop continues whilst a larger subtree is too big. When it reduces in size to contain $\le\frac {2}{3}L$ leaves, then it must contain at least $\frac {1}{3}L$ leaves, because the previous tree had more than $\frac {2}{3}L$ leaves. Observe, that at step 2 the current node cannot be a leaf, since at this point a (sub)tree rooted at the current node has more than $\frac {2}{3}L$ leaves.

The presented algorithm leverages the heavy-light decomposition technique.

Problem B-1

a.

We form a rooted tree by picking any node $v \in V$ as a root node. Edges in such a tree are incident on nodes from adjacent levels, so we can color a tree by levels. We need 2 colors in total, as the parity of a level determines its color.

b.

(1) -> (2)

Any bipartite graph's vertices may be partitioned into two subsets, such that no two distinct vertices from the same subset are connected by an edge. Therefore, we need 2 colors in total, one per subset.

(2) -> (3)

Suppose, for contradiction, that a 2-colorable graph $G$ has a cycle of odd length $p=\braket{v_0,v_1,...,v_{2k},v_{2k+1}=v_0}$. WLOG assume that this cycle is simple; otherwise, consider its simple sub-cycle of odd length or simplify the cycle if all sub-cycles are of even length (see Exercise B.4-2). We must ensure that $c(v_{2i+1}) \neq c(v_{2i})$ for all $i=0,1,...,k$. But this is impossible, since we cannot assign two different colors to $v_0$.

(3) -> (1)

Assume that graph $G$ is connected, otherwise apply the reasoning depicted below for each connected component. It is trivial to merge subsets of vertices from individual connected components into two major subsets for a whole graph $G$, as there is no interaction between them.

Pick any vertex $v \in V$ and select all vertices $u \in V$ reachable from $v$ via simple paths of even length. Notice that this includes $v$, as any vertex is reachable from itself through a 0-length path. Denote this subset as $V_1$. Form subset $V_2$ containing vertices reachable from $v$ via simple paths of odd length. We claim that all edges of graph $G$ are between vertices from these separate groups as well as no single vertex belongs to both subsets.

Assume, for contradiction, that there is a vertex $x \in V_1 \cap V_2$. But this is impossible, since there would be a cycle of odd length $v \overset{p'}{\leadsto} x \overset{p''}{\leadsto} v$, by choosing paths $p'$ and $p''$ of even and odd length, respectively.

Assume, for contradiction, that there are distinct vertices $x,y \in V_1$ connected by an edge (a simple path of odd length). But this is again impossible, since paths $v \leadsto x \to y$ and $v \leadsto y \to x$ would be of odd length, so $V_1 \cap V_2 \neq \empty$. The same reasoning apples for members of $V_2$. Therefore, graph $G$ is bipartite.

c.

We proceed by induction on $|V|$. The base case is when $|V|=1$, so we need 1 color. Thus, the base case is true, since we cannot have self-loops in an undirected graph.

For the inductive step take $|V|>1$ and assume it is true for all undirected graphs with less than $|V|$ vertices. Pick a vertex $v \in V$ and form an induced graph $G'=(V-\{v\},E')$ of $G$. Let $d'$ be the maximum degree of any vertex in $G'$. By the inductive hypothesis graph $G'$ is colorable with $d'+1$ colors, where $d'\le d$. A degree of vertex $v$ is at most $d$, so coloring its neighbors demand at most $d$ colors. Therefore, we can allocate an unused color to $v$, so graph $G$ is colorable with $d+1$ colors.

d.

Assume we need $k \ge 2$ colors for coloring a graph $G$. Consequently, all color combinations are required, otherwise there would be two colors that are indistinguishable from each other. We have ${k \choose 2} =\frac{(k-1)k}{2}\le |E|$ and $k\ge2 \implies \frac{k}{2} \le k-1$.

$$\begin{align*} k^2&=4\bigg(\frac{k}{2}\bigg)^2 \\ &\le4\frac{(k-1)k}{2} \\ &\le4|E| \\ &\therefore k^2=O(|V|) \implies k=O(\sqrt {|V|}) \end{align*}$$

Problem B-2

a.

In an undirected graph $G=(V,E)$ of size $|V|\ge2$ there are at least two vertices of the same degree.

Proof We prove this using the pigeonhole principle. A degree of a vertex may take values from the interval $[0,|V|-1]$. If we have an isolated vertex, then the rest of the $|V|-1$ vertices can take degrees from the range $[1,|V|-2]$. Clearly, we cannot avoid duplication of degrees. If there is no isolated vertex, then the range for degrees changes into $[1,|V|-1]$ that must be distributed onto $|V|$ vertices. Again, this cannot be done without a duplicated degree.

b.

In an undirected graph $G=(V,E)$ of size $|V|=6$ there is either a clique or isolated vertex set of size at least 3.

Proof Pick any vertex $v \in V$. From the remaining 5 vertices we can select 3 of them satisfying one of the following two conditions:

1. All of them are adjacent to $v$.

2. None of them are adjacent to $v$.

Case 1

If any pair from this group is adjacent, then that pair together with $v$ form a clique. Otherwise, they form an isolated vertex set.

Case 2

If all of them are adjacent to each other, then they form a clique. Otherwise, there must be 2 vertices not connected by an edge, so they together with $v$ form an isolated vertex set.

c.

Any undirected graph $G=(V,E)$ has a cut such that for any vertex $v \in V$ at least half of its neighbors do not belong to the same subset where $v$ belongs.

Proof We prove the statement by an explicit construction of the required cut.

1. Arbitrarily split vertices into two disjoint subsets $S$ and $T$ and initialize the cut-set.

2. If there is a vertex $v \in S$ with more than half of its neighbors also belonging to $S$, then move this vertex into $T$. Update the cut-set to reflect the new state.

3. If there is a vertex $v \in T$ with more than half of its neighbors also belonging to $T$, then move this vertex into $S$. Update the cut-set to reflect the new state.

4. If the cut-set was updated, then repeat steps 2-3.

Updates in steps 2-3 only increase the size of the cut-set. Therefore, the algorithm must terminate, as there are finite number of edges in a graph $G$.

Observe that at any moment in time $(V=S \cup T) \land (S \cap T=\empty)$, since vertices are shuffled around between disjoint sets. At exit, all vertices satisfy the required constraint.

d.

This is Dirac's theorem on Hamiltonian cycles and the proof has two parts:

1. Proving that there is a Hamiltonian path in a graph $G$, which is elaborated in the attached PDF document. It was retrieved on July, 2025 from here.

2. Proving that the above path is a cycle.

41KB

dirac.pdf

PDF

Open

Suppose we have a Hamiltonian path $p=\braket{v_1,v_2,...,v_n}$. If $\{v_1,v_n\} \in E$, then just append $v_1$ to the path to get a cycle. Otherwise, create two sets of indices indicating neighbors of $v_1$ and $v_n$, as follows:

$$\begin{align*} S_1&=\{i:2 \le i <n \land \{v_1,v_i\} \in E\} \\ S_2&=\{i:2 < i \le n \land \{v_{i-1},v_n\} \in E\} \\ (|S_1|=degree(v_1) &\land |S_2|=degree(v_n)) \implies |S_1|+|S_2| \ge n \land |S_1 \cup S_2| \le n-1 \\ &\therefore |S_1 \cap S_2| \neq \empty \quad \text {(by the pigeonhole principle)} \end{align*}$$

Let $i$ be the common index. The desired cycle is $v_1 \leadsto v_{i-1} \to v_n \leadsto v_i \to v_1$.

Problem B-3

a.

Assume that $n>1$. The solution is nearly identical to Exercise B.5-8, so will not be repeated here. Instead of number of leaves we count the number of nodes in subtrees. When the modified algorithm terminates at a subtree rooted at node $x$, then its size lies in the interval $[n/4,3n/4]$. So, by removing the edge connecting it to its parent we would get the desired split.

b.

An example of a simple binary tree whose most evenly balanced partition upon removal of a single edge has $|A|=3n/4$.

c.

We proceed by explicitly showing how to generate the required sets. It is based on the heavy-light decomposition technique as in Part (a). Let $T=(V,E)$ represent the input binary tree with with $n>1$ nodes. The steps of the the algorithm are as follows:

1. Initialize $m=\lfloor n/2 \rfloor$ and an empty set $A$ that will hold nodes of $T$.

2. Let the current node become the root of $T$.

3. Take the children of the current node.

4. Choose the larger child $C$ based on number of nodes and let the current node become its root.

5. If $C$ has more than $m$ nodes, then goto step 3.

6. Insert the nodes of $C$ into $A$.

7. Set $m=m -|C|$.

8. Remove the edge connecting $C$ to its parent, thus prune $T$.

9. If $m>0$, then goto step 2.

10. Output $A$ and $B=V-A$.

Each iteration removes a subtree of size at least half the remaining target, i.e., reducing $m$ by at least half each time. Thus, the number of edges removed is $O(\lg {\lfloor n/2 \rfloor})=O(\lg n)$. The heavy-light traversal ensures that in any subtree larger than $m$, at least one child is sufficiently large ($\ge m/2)$, guaranteeing progress toward the target without overshooting.