Discrete Structure (2013 AD onward)

Shortest path problem. Given a weighted graph and two vertices, find a path between them whose total edge weight is minimum. Dijkstra's algorithm solves it from a source vertex to all other vertices when all weights are non-negative.

Dijkstra's algorithm (source $A$).

1. Set $d(A)=0$ and $d(v)=\infty$ for all other $v$; mark all vertices unvisited.
2. Choose the unvisited vertex $u$ with the smallest $d(u)$ and mark it visited (permanent).
3. For each unvisited neighbour $v$ of $u$, if $d(u)+w(u,v)<d(v)$, set $d(v)=d(u)+w(u,v)$ and record $u$ as the predecessor of $v$.
4. Repeat steps 2 and 3 until all vertices are visited.

The final labels $d(v)$ are the shortest distances from $A$, and following the predecessors back from $v$ to $A$ gives the shortest path. In the table of iterations, each row shows the labels after one vertex is made permanent, and the vertex chosen in each row is the one with the least tentative label, so the distances are fixed in increasing order.

Dijkstra's algorithm finds the shortest paths from a source in a weighted graph with non-negative weights.

Procedure for source $A$ and target $F$

1. Set $d(A)=0$ and $d(v)=\infty$ for all other vertices; all vertices are unmarked (temporary).
2. Pick the unmarked vertex $u$ with the smallest $d(u)$ and mark it permanent.
3. For every neighbour $v$ of $u$, relax: if $d(u)+w(u,v)<d(v)$, set $d(v)=d(u)+w(u,v)$ and record $u$ as the predecessor of $v$.
4. Repeat steps 2 and 3 until $F$ is marked permanent.
5. The shortest distance is $d(F)$; the path is found by following predecessors from $F$ back to $A$.

Working table. Each round fixes one vertex (the one with the smallest label in the current row) and updates the labels of its neighbours. Carrying out the rounds on the weights in the figure fixes the vertices in the order of increasing distance from $A$, and the label of $F$ when it is fixed gives the shortest distance from $A$ to $F$, with the predecessor chain giving the path.

Dijkstra's algorithm (source $a$):

1. Set $d(a)=0$ and $d(v)=\infty$ for every other vertex; mark all vertices unvisited.
2. Choose the unvisited vertex $u$ with the smallest $d(u)$ and mark it visited (permanent).
3. For every unvisited neighbour $v$ of $u$ with edge weight $w(u,v)$: if $d(u)+w(u,v)<d(v)$, set $d(v)=d(u)+w(u,v)$ and record $u$ as the predecessor of $v$.
4. Repeat steps 2 and 3 until every vertex (or the target) is visited.

Starting from $a$, the first vertex made permanent is $a$ with label 0, its neighbours are labelled by the weights of their edges from $a$, and the process continues with the least labelled vertex each time, updating labels of its neighbours whenever a shorter route is found. When $d$ is made permanent, the label of $d$ is the length of the shortest path from $a$ to $d$, and the path itself is obtained by following the predecessors back from $d$ to $a$. The same final labels give the shortest distances from $a$ to all the remaining vertices.

A weighted graph is a graph in which each edge $e$ is assigned a non-negative number $w(e)$ (its weight, e.g. distance or cost). The length of a path is the sum of the weights of its edges.

Dijkstra's algorithm (shortest path from $a$ to $z$):

1. Set $d(a)=0$ and $d(v)=\infty$ for all other vertices; all vertices are unvisited.
2. Pick the unvisited vertex $u$ with the smallest $d(u)$ and mark it visited.
3. For each unvisited neighbour $v$ of $u$, if $d(u)+w(u,v)<d(v)$ set $d(v)=d(u)+w(u,v)$ and record $u$ as its predecessor.
4. Repeat steps 2-3 until $z$ is visited; $d(z)$ is the shortest distance and the predecessors give the path.

Illustration with edges $ab=2,\ ac=4,\ bc=1,\ bd=7,\ cd=3,\ cz=8,\ dz=2$:

Shortest path: $a\to b\to c\to d\to z$ with length $2+1+3+2=8$. The same steps applied to the weights in the given figure yield its shortest path.

Let $p$ be the number of pendant vertices (degree 1). Then

$n=2+1+3+p=6+p,\qquad |E|=n-1=5+p.$

By the handshaking lemma:

$2(5+p)=2\cdot2+1\cdot3+3\cdot4+p\cdot1=19+p\;\Rightarrow\;10+2p=19+p\;\Rightarrow\;p=9.$

The tree has 9 pendant vertices.

Definition. A forest is an acyclic graph, that is, a graph with no cycles. Equivalently, it is a disjoint union of trees; each connected component of a forest is a tree.

Example: the graph with edges $ab,\ bc$ and $de$ on vertices $a,b,c,d,e$ is a forest with two components (the path $a-b-c$ and the edge $d-e$).

Theorem. A forest with $n$ vertices and $k$ components has $n-k$ edges.

Proof. Let the components be trees $T_1,\dots,T_k$ with $n_1,\dots,n_k$ vertices, so $n_1+\dots+n_k=n$. A tree with $n_i$ vertices has exactly $n_i-1$ edges. Therefore the total number of edges is

$\sum_{i=1}^{k}(n_i-1)=\sum_{i=1}^{k}n_i-k=n-k.\qquad\blacksquare$

Binomial theorem. For a positive integer $n$,

$(a+b)^n=\sum_{r=0}^{n}\binom{n}{r}a^{n-r}b^{r}.$

Middle terms of $\left(2x+\dfrac{1}{3x}\right)^{15}$. There are 16 terms, so the middle terms are the 8th and 9th. The general term is

$T_{r+1}=\binom{15}{r}(2x)^{15-r}\left(\frac1{3x}\right)^{r}$

For $r=7$:

$T_8=\binom{15}{7}\frac{2^{8}}{3^{7}}x^{8-7}=\frac{6435\cdot256}{2187}\,x=\frac{183040}{243}\,x$

For $r=8$:

$T_9=\binom{15}{8}\frac{2^{7}}{3^{8}}x^{7-8}=\frac{6435\cdot128}{6561}\,\frac1x=\frac{91520}{729x}$

A forest is an acyclic graph (not necessarily connected); each of its components is a tree.

Theorem. A forest with $n$ vertices and $k$ components has $n-k$ edges.

Proof. Let the components be trees $T_1,\dots,T_k$ with $n_1,\dots,n_k$ vertices, so $n_1+\dots+n_k=n$. A tree with $n_i$ vertices has $n_i-1$ edges. Hence the total number of edges is

$\sum_{i=1}^k (n_i-1)=\sum_{i=1}^k n_i-k=n-k. \qquad\blacksquare$

Binomial theorem: for a positive integer $n$,

$(a+b)^n=\sum_{r=0}^{n}C(n,r)\,a^{n-r}b^{r}.$

The general term is $T_{r+1}=C(n,r)a^{n-r}b^r$.

Middle terms of $\left(2x^2-\dfrac1{3x}\right)^7$:

Here $n=7$ (odd), so there are 8 terms and two middle terms: $T_4$ and $T_5$.

$T_{r+1}=C(7,r)(2x^2)^{7-r}\left(-\frac1{3x}\right)^r.$

For $r=3$:

$T_4=C(7,3)(2x^2)^4\left(-\frac{1}{3x}\right)^3=35\cdot16x^8\cdot\left(-\frac{1}{27x^3}\right)=-\frac{560}{27}x^5.$

For $r=4$:

$T_5=C(7,4)(2x^2)^3\left(-\frac{1}{3x}\right)^4=35\cdot8x^6\cdot\frac{1}{81x^4}=\frac{280}{81}x^2.$

Middle terms: $-\dfrac{560}{27}x^5$ and $\dfrac{280}{81}x^2$.

Let $P(n)$: $n^3+2n$ is divisible by 3.

Basis: $n=1$: $1+2=3$, divisible by 3.

Inductive step: assume $k^3+2k=3m$ for some integer $m$. Then

$(k+1)^3+2(k+1)=k^3+3k^2+3k+1+2k+2=(k^3+2k)+3(k^2+k+1)=3m+3(k^2+k+1),$

which is divisible by 3. So $P(k)\Rightarrow P(k+1)$, and by induction $n^3+2n$ is divisible by 3 for all $n\ge1$. $\blacksquare$

Let $P(n)$: $n^3+2n$ is divisible by 3.

Basis step: $P(1)$: $1^3+2\cdot1=3=3\cdot1$, divisible by 3.

Inductive hypothesis: assume $P(k)$ is true for some $k\ge1$, i.e. $k^3+2k=3m$ for some integer $m$.

Inductive step: consider $n=k+1$:

$(k+1)^3+2(k+1)=k^3+3k^2+3k+1+2k+2=(k^3+2k)+3k^2+3k+3$ $=3m+3(k^2+k+1)=3\,(m+k^2+k+1).$

This is divisible by 3, so $P(k+1)$ holds. By the principle of mathematical induction, $n^3+2n$ is divisible by 3 for every integer $n\ge1$. $\blacksquare$

Binomial theorem: for any positive integer $n$,

$(a+b)^n=\sum_{r=0}^{n}\binom{n}{r}a^{\,n-r}b^{\,r}.$

Coefficient of $x^2$ in $\left(2x^2-\dfrac{1}{3x}\right)^7$: the general term is

$T_{r+1}=\binom7r(2x^2)^{7-r}\left(-\frac1{3x}\right)^r=\binom7r2^{7-r}\left(-\frac13\right)^r x^{14-3r}.$

Setting $14-3r=2$ gives $r=4$. Then

$T_5=\binom74\,2^{3}\left(\frac13\right)^4=35\cdot8\cdot\frac1{81}=\frac{280}{81}.$

The coefficient of $x^2$ is $\dfrac{280}{81}$.

A forest is a graph with no cycles; each of its $k$ components is a tree.

Let the components be $T_1,\dots,T_k$ with $n_1,\dots,n_k$ vertices, so $n_1+\cdots+n_k=n$. A tree with $n_i$ vertices has exactly $n_i-1$ edges. Hence the number of edges is

$\sum_{i=1}^{k}(n_i-1)=\sum_{i=1}^k n_i-k=n-k. \qquad\blacksquare$

(For $k=1$ the forest is a tree with $n-1$ edges.)

Let $p$ be the number of pendant vertices (degree 1). Then $n=3+4+p=7+p$ and the tree has $n-1=6+p$ edges.

Handshaking lemma: $3(2)+4(3)+p(1)=2(6+p)$, i.e. $18+p=12+2p$, so $p=\mathbf{6}$.

Let $P(n)$: $n^3+2n$ is divisible by 3, for $n\ge1$.

Basis step. For $n=1$: $1+2=3$, which is divisible by 3. So $P(1)$ is true.

Inductive step. Assume $P(k)$, that is, $k^3+2k=3m$ for some integer $m$. Then

$(k+1)^3+2(k+1)=k^3+3k^2+3k+1+2k+2=(k^3+2k)+3(k^2+k+1)$

$=3m+3(k^2+k+1)=3\,(m+k^2+k+1)$

which is divisible by 3. So $P(k)\to P(k+1)$.

By mathematical induction, $n^3+2n$ is divisible by 3 for all positive integers $n$. $\blacksquare$

A directed graph is strongly connected if for every ordered pair of vertices $u,v$ there is a directed path from $u$ to $v$ (and hence, applying this to both orders, also from $v$ to $u$).

Example: the digraph with vertices $a,b,c$ and arcs $a\to b,\ b\to c,\ c\to a$ is strongly connected, since going around the directed cycle reaches any vertex from any other.

Let $P(n)$ be the statement $n<2^n$.

Basis. $P(0)$: $0<2^0=1$, true.

Inductive step. Assume $P(k)$ for some $k\ge0$, i.e. $k<2^k$. Then $k+1<2^k+1\le 2^k+2^k=2^{k+1},$ using $1\le2^k$ for $k\ge0$. So $P(k+1)$ holds.

By induction, $n<2^n$ for all $n\ge0$.

Let the conditional be $p\to q$, with contrapositive $\neg q\to\neg p$.

$\neg q\to\neg p\equiv \neg(\neg q)\vee\neg p\equiv q\vee\neg p\equiv\neg p\vee q\equiv p\to q$

Truth table:

The columns are identical, so a conditional statement is logically equivalent to its contrapositive.

The 12 numbers are placed in the 12 distinct positions of the clock face, which can be done in

$12!=479{,}001{,}600\text{ ways.}$

(If arrangements differing only by rotation were counted as the same, the count would be $11!=39{,}916{,}800$.)

A binary tree of height $h$ has at most $2^{h+1}-1$ vertices. For 63 vertices we need $2^{h+1}-1\ge63$, so $2^{h+1}\ge64$ and $h\ge5$.

The minimum possible height is 5 (the complete binary tree with $2^6-1=63$ vertices has exactly this height).

A relation from $A$ to $B$ is any subset of $A\times B$. Since $|A\times B|=mn$, the number of subsets is

$2^{mn}.$

The 12 numbers are placed around a circle, where only the relative order matters (rotations give the same arrangement). The number of circular arrangements of 12 distinct objects is

$(12-1)!=11!=39{,}916{,}800.$

By Cayley's formula, the number of spanning trees of $K_n$ is $n^{n-2}$. For $K_5$:

$5^{3}=125.$

Let $P(n):\ 2+4+6+\dots+2n=n(n+1)$.

Basis. $n=1$: LHS $=2$, RHS $=1\cdot2=2$. True.

Step. Assume $P(k)$: $2+4+\dots+2k=k(k+1)$. Then

$2+4+\dots+2k+2(k+1)=k(k+1)+2(k+1)=(k+1)(k+2),$

which is $P(k+1)$. By induction, $P(n)$ is true for all $n\ge1$. $\blacksquare$

Row 6 of Pascal's triangle is $1,\ 6,\ 15,\ 20,\ 15,\ 6,\ 1$. Taking $a=1,\ b=2x$:

$(1+2x)^6=1+6(2x)+15(2x)^2+20(2x)^3+15(2x)^4+6(2x)^5+(2x)^6$

$=1+12x+60x^2+160x^3+240x^4+192x^5+64x^6.$

Equivalence class. For an equivalence relation $R$ on a set $A$ and $a\in A$, the equivalence class of $a$ is $[a]=\{x\in A: xRa\}$, the set of all elements related to $a$. The classes form a partition of $A$, and conversely every partition defines an equivalence relation.

From the partition $P=\{\{2,5\},\{1,3\}\}$ of $A=\{1,2,3,5\}$, two elements are related when they lie in the same block:

$R=\{(2,2),(2,5),(5,2),(5,5),(1,1),(1,3),(3,1),(3,3)\}.$

This relation is reflexive, symmetric and transitive, and its classes are $[2]=[5]=\{2,5\}$ and $[1]=[3]=\{1,3\}$.

Let the conditional statement be $p\to q$ and its contrapositive $\neg q\to\neg p$.

The columns for $p\to q$ and $\neg q\to\neg p$ are identical, so $p\to q\equiv\neg q\to\neg p$.

Algebraically: $\neg q\to\neg p\equiv \neg(\neg q)\vee\neg p\equiv q\vee\neg p\equiv\neg p\vee q\equiv p\to q$. $\blacksquare$

The first bit is fixed as 1 and each of the other 7 bits can be 0 or 1, so the number is $2^7=128$.

Claim: a tree $T$ with $n\ge2$ vertices has at least two pendant vertices (vertices of degree 1).

Proof 1 (degree sum). A tree with $n$ vertices has $n-1$ edges, so $\sum\deg(v)=2(n-1)=2n-2$. Since $T$ is connected and $n\ge2$, every vertex has degree $\ge1$. Suppose at most one vertex has degree 1. Then the other $n-1$ vertices have degree $\ge2$, and

$\sum\deg(v)\ge 1+2(n-1)=2n-1>2n-2,$

a contradiction. Hence at least two vertices have degree 1.

Proof 2 (longest path). Take a longest path $v_0v_1\cdots v_k$ in $T$ ($k\ge1$). If $v_0$ had another neighbour, it would either be on the path (forming a cycle, impossible in a tree) or off the path (giving a longer path). So $\deg v_0=1$; similarly $\deg v_k=1$. These are two distinct pendant vertices. $\blacksquare$

A spanning tree of a connected graph $G$ is a subgraph that is a tree and contains all the vertices of $G$ (it has $n-1$ edges).

By Cayley's formula, the complete graph $K_n$ has $n^{\,n-2}$ spanning trees.

There are 4 suits. In the worst case we pick 2 cards from each suit, i.e. $4\times2=8$ cards, without having 3 of one suit. The next card must give 3 of some suit. By the pigeonhole principle, $8+1=9$ cards must be selected.

The first bit is 0 and the last bit is 1, so the 3 middle bits are free: $2^3=8$ strings.

In a full binary tree every internal vertex has 2 children. With $n=15$ vertices, the number of internal vertices is $i=\dfrac{n-1}{2}=7$ and leaves $=8$.

• Minimum height: the tree is as bushy as possible (a complete binary tree): $2^{h+1}-1=15\Rightarrow h=3$.
• Maximum height: a chain where each internal vertex has one leaf child: $n=2h+1\Rightarrow h=7$.

Minimum height $=3$, maximum height $=7$.

Proof. Let $T$ be a tree with $n>2$ vertices. Since $T$ is connected and has at least one edge, take a longest path $P=v_0v_1\cdots v_k$ in $T$ ($k\ge 2$ because $n>2$).

Suppose $v_0$ has a neighbour $w$ other than $v_1$.

• If $w$ is on $P$, then $w$ together with the part of $P$ up to $w$ forms a cycle, impossible in a tree.
• If $w$ is not on $P$, then $wv_0v_1\cdots v_k$ is a longer path, contradicting the choice of $P$.

So $\deg(v_0)=1$. By the same argument $\deg(v_k)=1$. Since $v_0\neq v_k$, the tree has at least two pendant vertices. $\blacksquare$

(Alternative: if at most one vertex had degree 1, then $\sum\deg\ge 1+2(n-1)=2n-1>2(n-1)$, contradicting $\sum\deg=2(n-1)$.)

The relation is "$a\,R\,b$ iff $a$ and $b$ lie in the same block". Each block $S$ contributes $S\times S$:

$R=\{(1,1),(1,4),(4,1),(4,4)\}\cup\{(2,2),(2,3),(3,2),(3,3)\}\cup\{(5,5)\}$

So $R=\{(1,1),(1,4),(4,1),(4,4),(2,2),(2,3),(3,2),(3,3),(5,5)\}$, which is reflexive, symmetric and transitive.

A relation on a set with $N$ elements is a subset of $A\times A$, which has $N^2$ elements. Each ordered pair is either in or out of the relation, so the number of relations is $\mathbf{2^{N^2}}$.

The deck has 13 diamonds and 39 non-diamonds. In the worst case all 39 non-diamonds are chosen first, and then 3 diamonds are needed:

$39+3=\mathbf{42}$

cards must be selected (generalised pigeonhole principle).

Row 6 of Pascal's triangle is $1,6,15,20,15,6,1$. With $a=1$, $b=-2x$:

$(1-2x)^6=1-6(2x)+15(2x)^2-20(2x)^3+15(2x)^4-6(2x)^5+(2x)^6$

$=1-12x+60x^2-160x^3+240x^4-192x^5+64x^6 .$

A relation $R$ on $A$ is not antisymmetric when there exist distinct elements $a\neq b$ in $A$ such that both $(a,b)\in R$ and $(b,a)\in R$.

For every real $x$, $\lfloor x\rfloor\le x\le\lceil x\rceil$, so $\lfloor x\rfloor-1<\lceil x\rceil$ always. The two sides can never be equal.

Hence there is no real number $x$ for which $\lfloor x\rfloor-1=\lceil x\rceil$.

An $r$-permutation of a set of $n$ distinct objects is an ordered arrangement of $r$ of the objects. Their number is $P(n,r)=\dfrac{n!}{(n-r)!}$.

A loop is an edge that joins a vertex to itself, i.e. an edge whose two end points are the same vertex.

A graph $G$ is connected if there is a path between every pair of distinct vertices of $G$. Otherwise it is disconnected.

A connected multigraph is traversable if it has a path (trail) that uses every edge exactly once.

By Euler's theorem this holds exactly when the graph has either no odd-degree vertices (the trail can be closed, an Euler circuit) or exactly two odd-degree vertices (an Euler trail from one to the other).

A spanning tree of the cycle $C_5$ is obtained by deleting exactly one of its $5$ edges. Hence it has 5 different spanning trees.

A tree with $n$ vertices has $n-1$ edges.

$R$ is reflexive exactly when every vertex of the digraph has a loop (an arrow from the vertex to itself), because reflexivity needs $(a,a)\in R$ for every $a\in A$.

A binary relation from a set $A$ to a set $B$ is a subset $R$ of the Cartesian product $A\times B$; $(a,b)\in R$ is written $aRb$.

Take $R=\{(a,b),(a,c),(a,d),(b,d),(c,d)\}$ on $A=\{a,b,c,d\}$.

• Reflexive: No, since $(a,a)\notin R$.
• Irreflexive: Yes, no pair $(x,x)$ is in $R$.
• Symmetric: No, $(a,b)\in R$ but $(b,a)\notin R$.
• Asymmetric: Yes, whenever $(x,y)\in R$ we have $(y,x)\notin R$.
• Antisymmetric: Yes, there is no pair of distinct elements related both ways.
• Transitive: Yes. The only chains are $(a,b),(b,d)$ and $(a,c),(c,d)$, both requiring $(a,d)$, which is in $R$.

A bijection is a function that is both one-to-one (injective) and onto (surjective).

Here $f(a)=\sqrt{a+1}$ with $A=\{a\in\mathbb R: a\ge-1\}$ and $B=\{x\in\mathbb R: x\ge0\}$.

One-to-one. If $\sqrt{a_1+1}=\sqrt{a_2+1}$, squaring gives $a_1=a_2$.

Onto. For any $y\ge0$ take $a=y^2-1\ge-1$; then $f(a)=\sqrt{y^2}=y$.

So $f$ is a bijection and therefore invertible. From $y=\sqrt{a+1}$ we get $a=y^2-1$, so $f^{-1}(y)=y^2-1,\qquad y\ge 0 .$

A sequence is an ordered list of terms $a_1,a_2,a_3,\dots$, formally a function from a set of consecutive integers (usually $\mathbb Z^+$) to a set.

Difference. A string is a finite sequence of symbols taken from an alphabet. A sequence may be finite or infinite, whereas a string is always finite.

Length of a finite string is the number of symbols (terms) it contains, counted with repetition; e.g. $abba$ has length $4$.

Denumerability. The infinite sequence of positive even integers is $2,4,6,\dots$. Define $f:\mathbb Z^+\to E$ (where $E$ is the set of positive even integers) by $f(n)=2n$.