Discrete Structure (2005–2012 AD)

Dijkstra's algorithm (source $A$, weights $w(u,v)\ge 0$):

1. Set $d(A)=0$ and $d(v)=\infty$ for every other vertex. Mark all vertices as unvisited.
2. Pick the unvisited vertex $u$ with the smallest $d(u)$ and mark it permanent (visited).
3. For every unvisited neighbour $v$ of $u$, if $d(u)+w(u,v)<d(v)$, then 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 permanent.

At the end, $d(v)$ is the length of the shortest path from $A$ to $v$, and following the predecessors back from $v$ to $A$ gives the path itself.

For the graph with vertices $a,b,c,d,e$, record each step in a table with one column per vertex. Start with $0,\infty,\infty,\infty,\infty$, make $a$ permanent, update its neighbours, then repeatedly make the vertex with the least label permanent and relabel its neighbours. The last row of labels gives the shortest distances from $A$ to $b,c,d,e$.

Dijkstra's algorithm (source $a$, non-negative weights):

1. Set $d(a)=0$, $d(v)=\infty$ for all other vertices, and mark all vertices unvisited.
2. Choose the unvisited vertex $u$ with the least label $d(u)$ and make it 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 from step 2 until all vertices are permanent.

For the graph with vertices $a,b,c,d,e,f$, tabulate the labels of $b,c,d,e,f$ after each step. The label of each vertex when it becomes permanent is the length of the shortest path from $a$ to it, and the shortest path itself is read off by following the recorded predecessors back to $a$.

Dijkstra's algorithm from source $A$:

1. Give $A$ the label $0$ and every other vertex the label $\infty$.
2. Make permanent the temporary-labelled vertex $u$ with the smallest label.
3. For each neighbour $v$ of $u$ that is not permanent, replace its label by $\min\big(\text{label}(v),\ \text{label}(u)+w(u,v)\big)$, remembering the predecessor.
4. Repeat steps 2 and 3 until all vertices are permanent.

At the end, each label is the shortest distance from $A$, and following the predecessors back from any vertex gives its shortest path.

The weighted graph on vertices $A$ to $G$ is given in a figure in the original paper, which is not reproduced here, so the particular distances and paths cannot be stated.

Dijkstra's algorithm (source $a$, weights $w(u,v)\ge 0$):

1. Set $d(a)=0$ and $d(v)=\infty$ for all other vertices; all vertices are temporary.
2. Make permanent the temporary vertex $u$ with the smallest $d(u)$.
3. For each temporary 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 and 3 until all of $b,\dots,f$ are permanent.

For the given weighted graph, form a table with a column for each of $a,b,c,d,e,f$. The first row is $0,\infty,\infty,\infty,\infty,\infty$. Make $a$ permanent and label its neighbours with the edge weights, then at each later row fix the smallest temporary label and relabel its neighbours using step 3. The final labels are the shortest distances from $a$ to $b,c,d,e,f$, and tracing the predecessors back from each vertex to $a$ gives the corresponding shortest path.

(a) Hamiltonian but not Eulerian. Take the 6-cycle $v_1v_2v_3v_4v_5v_6v_1$ and add the chord $v_1v_4$. The cycle $v_1v_2v_3v_4v_5v_6v_1$ visits every vertex once, so the graph is Hamiltonian. But $v_1$ and $v_4$ have degree 3 (odd), so it has no Euler circuit and is not Eulerian.

(b) Eulerian but not Hamiltonian. Take the complete bipartite graph $K_{2,4}$ with parts $\{u_1,u_2\}$ and $\{w_1,w_2,w_3,w_4\}$. The degrees are $4$ for $u_1,u_2$ and $2$ for each $w_i$, all even, and the graph is connected, so it has an Euler circuit, e.g. $u_1w_1u_2w_2u_1w_3u_2w_4u_1$. A Hamiltonian cycle would alternate between the two parts, so it would need as many vertices in each part, but the parts have 2 and 4 vertices. Hence it is not Hamiltonian.

(i) Hamiltonian but not Eulerian: take the 6-cycle $v_1v_2v_3v_4v_5v_6v_1$ and add the chord $v_1v_4$. The cycle visits every vertex once, so the graph is Hamiltonian. But $v_1$ and $v_4$ now have degree 3 (odd), so no Eulerian circuit exists.

(ii) Eulerian but not Hamiltonian: take $K_{2,4}$, with vertices $x,y$ each joined to all of $w_1,w_2,w_3,w_4$. Here $\deg x=\deg y=4$ and $\deg w_i=2$, all even and the graph is connected, so it is Eulerian. A Hamiltonian cycle would have to alternate between the two sides, which needs equal numbers of vertices on each side, but the sides have 2 and 4. So it is not Hamiltonian.

Difference. A Hamiltonian graph has a cycle passing through every vertex exactly once. An Eulerian graph has a closed trail (circuit) passing through every edge exactly once; a connected graph is Eulerian iff all vertex degrees are even.

Let the six vertices be $1,\dots,6$.

(a) Hamiltonian but not Eulerian. The 6-cycle $1\text{-}2\text{-}3\text{-}4\text{-}5\text{-}6\text{-}1$ plus the chord $14$. The cycle is a Hamiltonian cycle, but vertices 1 and 4 have degree 3 (odd), so there is no Euler circuit.

(b) Eulerian but not Hamiltonian. A triangle $v,a,b$ and a 4-cycle $v,c,d,e$ sharing the vertex $v$. All degrees are even ($v$ has degree 4, others 2), so an Euler circuit exists. But $v$ is a cut vertex, so no cycle can visit all six vertices; there is no Hamiltonian cycle.

(c) Both. The 6-cycle $C_6$: every degree is 2 (Eulerian) and the cycle itself passes through all vertices (Hamiltonian).

Combination. A combination of $r$ objects from $n$ distinct objects is a selection of $r$ of them in which order does not matter. The number is

$C(n,r)=\binom{n}{r}=\frac{n!}{r!\,(n-r)!}.$

Pigeonhole principle. If $n$ pigeons are placed in $k$ holes with $n>k$, some hole contains at least two pigeons. More generally, if $n$ objects are placed in $k$ boxes, some box contains at least $\lceil n/k\rceil$ objects.

Students. Treat the $12$ months as boxes. If there are $24$ students, two in each month is possible, so $24$ is not enough. With $2\cdot 12+1=25$ students, some month has at least $\lceil 25/12\rceil=3$ students.

The minimum number is 25.

Isomorphic graphs: graphs $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ are isomorphic if there is a bijection $\phi:V_1\to V_2$ such that $u,v$ are adjacent in $G_1$ iff $\phi(u),\phi(v)$ are adjacent in $G_2$. The bijection $\phi$ is the isomorphism.

Showing two graphs are not isomorphic: it is enough to find one property preserved by isomorphism on which they differ:

• the number of vertices, or the number of edges;
• the degree sequence;
• the presence of a cycle of a given length, or a circuit.

For $G_1$ and $G_2$ (both with 6 vertices), counting degrees shows that they have different degree sequences, or that one contains a cycle of a length the other lacks. For example, a vertex of degree 3 adjacent to a pendant vertex in one graph has no counterpart in the other. Since the invariant differs, no adjacency-preserving bijection can exist, so $G_1\not\cong G_2$.

Spanning tree: a subgraph of a connected graph $G$ that is a tree and contains all vertices of $G$.

Let the bow-tie have centre $c$ and triangles $c,a,b$ and $c,d,e$. It has 5 vertices, so each spanning tree has 4 edges. A tree must drop exactly one edge from each triangle, since dropping two from one triangle would disconnect a vertex. Each triangle has 3 ways to drop one edge, giving $3\times3=9$ spanning trees.

Choose the left part from $\{ca,cb\}$, $\{ca,ab\}$, $\{cb,ab\}$ and the right part from $\{cd,ce\}$, $\{cd,de\}$, $\{ce,de\}$. Every combination of one left choice and one right choice is a spanning tree:

1. $ca,cb,cd,ce$
2. $ca,cb,cd,de$
3. $ca,cb,ce,de$
4. $ca,ab,cd,ce$
5. $ca,ab,cd,de$
6. $ca,ab,ce,de$
7. $cb,ab,cd,ce$
8. $cb,ab,cd,de$
9. $cb,ab,ce,de$

Simple graph. A graph with no loops and no parallel (multiple) edges between any pair of vertices.

Multigraph. A graph that may have several edges joining the same pair of vertices (parallel edges); loops are allowed in some definitions.

Isolated vertex. A vertex of degree 0, that is, one not incident with any edge.

Theorem. In any graph the number of odd-degree vertices is even.

Proof. Each edge contributes 2 to the sum of the degrees, so

$\sum_{v\in V}\deg v=2|E|,$

which is even. Split the vertices into the set $O$ of odd-degree vertices and the set $E'$ of even-degree vertices:

$\sum_{v\in O}\deg v=2|E|-\sum_{v\in E'}\deg v=\text{even}.$

A sum of odd numbers is even only if the number of terms is even. Hence $|O|$ is even. $\blacksquare$

A full binary tree is a rooted tree in which every internal vertex has exactly two children (so every vertex has either $0$ or $2$ children).

Definition. If $g:A\to B$ and $f:B\to C$, the composition of $g$ followed by $f$ is the function $f\circ g:A\to C$ given by $(f\circ g)(x)=f(g(x))$. It is denoted $f\circ g$ (also written $fg$).

Here $f(x)=3x-4$ and $g(x)=\dfrac{x}{x-2}$, $x\ne2$.

$(f\circ g)(x)=f(g(x))=3\cdot\frac{x}{x-2}-4=\frac{3x-4x+8}{x-2}=\frac{8-x}{x-2},\quad x\neq2.$

$(g\circ f)(x)=g(f(x))=\frac{3x-4}{(3x-4)-2}=\frac{3x-4}{3x-6}=\frac{3x-4}{3(x-2)},\quad x\neq 2.$

Both compositions are defined for all real $x\ne2$ (for $g\circ f$ we need $f(x)\neq2$, i.e. $x\ne 2$).

Definition. An undirected graph $G=(V,E)$ consists of a set $V$ of vertices and a set $E$ of edges, each edge being an unordered pair of vertices. Example: $V=\{a,b,c,d\}$, $E=\{ab,bc,cd,da,ac\}$.

Theorem. In any graph, the number of vertices of odd degree is even.

Proof. By the handshaking lemma, $\sum_{v}\deg(v)=2|E|$, which is even. Split the vertices into $V_e$ (even degree) and $V_o$ (odd degree):

$\sum_{v\in V_e}\deg(v)+\sum_{v\in V_o}\deg(v)=2|E|.$

The first sum is a sum of even numbers, so it is even. Hence $\sum_{v\in V_o}\deg(v)=2|E|-(\text{even})$ is even. But it is a sum of $|V_o|$ odd numbers, and such a sum is even only if the number of terms is even. Therefore $|V_o|$ is even. $\blacksquare$

Regular graph. A graph in which every vertex has the same degree is regular; if that degree is $r$, it is $r$-regular.

Claim 1. An $r$-regular graph with $r$ odd has an even number of vertices.

Let there be $n$ vertices. The sum of degrees is $nr$, and by the handshaking lemma $nr=2|E|$, which is even. Since $r$ is odd, $n$ must be even. $\blacksquare$

Claim 2. The complete graph $K_n$ is regular of degree $n-1$.

In $K_n$ every vertex is joined by exactly one edge to each of the other $n-1$ vertices, and there are no loops or multiple edges. So every vertex has degree $n-1$, and $K_n$ is $(n-1)$-regular. $\blacksquare$

Definition. A tree is a connected graph with no cycles. A pendant vertex is a vertex of degree 1.

Theorem. A tree $T$ with $n\ge2$ vertices has at least two pendant vertices.

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

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

a contradiction. Therefore at least two vertices have degree 1. $\blacksquare$

(Alternatively, the end vertices of a longest path in $T$ are pendant, since any other neighbour of an end vertex would either extend the path or create a cycle.)

Claim. A graph $G$ is connected if and only if it has a subgraph that is a spanning tree.

($\Leftarrow$) Let $T$ be a spanning tree of $G$. $T$ contains all vertices of $G$ and is connected, so any two vertices of $G$ are joined by a path in $T$, which is also a path in $G$. Hence $G$ is connected.

($\Rightarrow$) Let $G$ be connected. If $G$ has no cycle, it is itself a tree and a spanning tree. Otherwise, choose a cycle and delete one of its edges. Removing an edge of a cycle does not disconnect the graph, since any path using that edge can go round the rest of the cycle. The resulting graph is still connected and spans all vertices. Repeat while cycles remain. Since $G$ has finitely many edges, the process ends with a connected graph with no cycles that contains all vertices, which is a spanning tree of $G$. $\blacksquare$

The relation determined by a partition relates two elements exactly when they lie in the same block. The block $\{1,2,3\}$ gives all 9 ordered pairs of its elements and the block $\{4\}$ gives $(4,4)$:

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

A set is countable if it can be put in one-to-one correspondence with the positive integers (or is finite). Define $f:\mathbb{Z}^+\to\{1,3,5,\dots\}$ by

$f(n)=2n-1.$

It is one-to-one, since $2n-1=2m-1$ gives $n=m$, and onto, since every odd positive integer $k$ equals $f\!\left(\frac{k+1}{2}\right)$. So the odd positive integers can be listed $1,3,5,7,\dots$ and the set is countable (countably infinite).

$|E(K_n)|=\frac{n(n-1)}{2}\Rightarrow |E(K_9)|=\frac{9\cdot8}{2}=36.$

Combination: a selection of $r$ objects from $n$ distinct objects in which order does not matter: $C(n,r)=\frac{n!}{r!(n-r)!}.$ For example, choosing 2 people from $\{A,B,C\}$ gives $C(3,2)=3$ selections: $AB, AC, BC$.

Pigeonhole principle: if more than $k$ objects are placed into $k$ boxes, some box contains at least two objects. More generally, if $N$ objects go into $k$ boxes, some box has at least $\lceil N/k\rceil$ objects.

Three in the same month: there are 12 months (boxes). With $24$ students, each month could hold exactly 2. With $2\cdot12+1=25$ students, some month must have at least $\lceil 25/12\rceil=3$.

The minimum number of students is 25.

Graph: $G=(V,E)$ with a non-empty set $V$ of vertices and a set $E$ of edges, each joining two vertices.

Trivial graph: a graph with a single vertex and no edges.

Theorem: the number of odd-degree vertices in a graph is even.

Proof: each edge adds 2 to the total degree, so $\sum_{v}\deg(v)=2|E|$, which is even. Let $V_e$ be the set of even-degree vertices and $V_o$ the set of odd-degree vertices. Then $\sum_{v\in V_o}\deg(v)=2|E|-\sum_{v\in V_e}\deg(v),$ which is even. A sum of odd numbers is even only if it has an even number of terms, so $|V_o|$ is even. $\blacksquare$

Tree: a connected graph with no cycles.

Spanning tree: a subgraph of $G$ that is a tree and contains all vertices of $G$.

Theorem: $G$ is connected iff it has a spanning tree.

Proof:

($\Leftarrow$) If $G$ has a spanning tree $T$, then $T$ is connected and contains every vertex, so any two vertices of $G$ are joined by a path in $T$, which is also a path in $G$. Hence $G$ is connected.

($\Rightarrow$) Let $G$ be connected. If $G$ has no cycle, it is already a tree and is its own spanning tree. Otherwise, pick a cycle and delete one of its edges. The graph stays connected, because any path through the deleted edge can go around the rest of the cycle, and no vertex is removed. Repeat while cycles remain. The process stops after finitely many steps and leaves a connected, acyclic graph on all the vertices, which is a spanning tree. $\blacksquare$

Use Kruskal's algorithm (or Prim's) on the weighted graph with vertices $A$ to $F$.

1. List all edges in increasing order of weight.
2. Add the smallest edge to the tree.
3. Take the next smallest edge and add it only if it does not form a cycle with the edges already chosen.
4. Stop when $6-1=5$ edges have been chosen.

The chosen 5 edges connect all six vertices, and their weight sum is the minimum possible. The tree has exactly $n-1=5$ edges.

Rooted tree: a tree in which one vertex is distinguished as the root. Every other vertex is reached from the root by a unique path. In an ordered rooted tree the children of each vertex are ordered, and the address of a vertex is its parent's address followed by its position among its siblings.

(a) Lexicographic order:

0, 1, 1.1, 2, 2.1, 2.1.1, 2.2, 2.2.1, 2.2.1.1, 3.1, 3.1.1.2, 3.2, 3.2.1, 3.2.1.1, 3.2.1.2

(b) Ordered rooted tree (the root is 0; indentation shows the parent-child relation):

0
├── 1
│   └── 1.1
├── 2
│   ├── 2.1
│   │   └── 2.1.1
│   └── 2.2
│       └── 2.2.1
│           └── 2.2.1.1
└── 3
    ├── 3.1
    │   └── 3.1.1
    │       └── 3.1.1.2
    └── 3.2
        └── 3.2.1
            ├── 3.2.1.1
            └── 3.2.1.2

The vertices 3, 3.1.1 (and 3.1.1.1) do not appear in the list, but they are the ancestors that connect the listed addresses to the root.

Function. A function $f$ from $A$ to $B$ is a rule that assigns to each element $a\in A$ exactly one element $f(a)\in B$. $A$ is the domain and $B$ the codomain.

Inverse of $f(x)=5x-3$. Put $y=5x-3$ and solve for $x$: $x=\dfrac{y+3}{5}$. Hence

$f^{-1}(x)=\frac{x+3}{5}.$

Check: $f(f^{-1}(x))=5\cdot\frac{x+3}{5}-3=x$.

Composition $g\circ f$.

$(g\circ f)(x)=g(f(x))=3(5x-3)-1=15x-10.$

Binomial theorem. For a positive integer $n$,

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

The numbers $\binom{n}{r}=\dfrac{n!}{r!(n-r)!}$ are the binomial coefficients; they form the rows of Pascal's triangle.

Middle terms. For $n=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(\frac{1}{2x}\right)^{r}=\binom{15}{r}(2x)^{15-2r}.$

• $r=7$: $T_8=\binom{15}{7}(2x)^{1}=6435\cdot 2x=12870\,x$.
• $r=8$: $T_9=\binom{15}{8}(2x)^{-1}=\dfrac{6435}{2x}$.

Rooted tree. A tree in which one vertex is designated the root, and every edge is directed away from the root. Each vertex other than the root has a unique parent. In an ordered rooted tree the children of each vertex are ordered, and the vertices are labelled by addresses (root $0$, its children $1,2,3,\dots$, the children of $a$ being $a.1,a.2,\dots$).

i. Lexicographic order.

$0,\ 1,\ 1.1,\ 1.1.1,\ 1.1.2,\ 2,\ 2.1,\ 2.1.1,\ 2.2,\ 2.2.1,\ 2.2.1.1,\ 3,\ 3.1,\ 3.2,\ 3.2.1,\ 3.2.1.1,\ 3.2.1.2.$

ii. Tree. The root $0$ has three children $1,2,3$.

• $1$ has child $1.1$, which has children $1.1.1$ and $1.1.2$.
• $2$ has children $2.1$ and $2.2$. $2.1$ has child $2.1.1$. $2.2$ has child $2.2.1$, which has child $2.2.1.1$.
• $3$ has children $3.1$ and $3.2$. $3.2$ has child $3.2.1$, which has children $3.2.1.1$ and $3.2.1.2$.

0
├─1 ─ 1.1 ─┬─ 1.1.1
│          └─ 1.1.2
├─2 ─┬─ 2.1 ─ 2.1.1
│    └─ 2.2 ─ 2.2.1 ─ 2.2.1.1
└─3 ─┬─ 3.1
     └─ 3.2 ─ 3.2.1 ─┬─ 3.2.1.1
                      └─ 3.2.1.2

It has 17 vertices and 16 edges, as a tree should.

A minimal spanning tree of a connected weighted graph with 5 vertices has 4 edges, and is built greedily (Kruskal or Prim).

Kruskal's method.

1. Sort all edges by increasing weight.
2. Take the next lightest edge; keep it if it joins two different components, and reject it if it would form a cycle.
3. Stop when 4 edges ($=n-1$) have been kept.

Prim's method. Start at any vertex, and repeatedly add the cheapest edge joining a vertex already in the tree to one outside it, until $a,b,c,d,e$ are all included.

The weights are in the figure of the original paper, which is not reproduced here. The tree obtained by either method has the same minimum total weight, equal to the sum of the four selected edge weights.

There are 12 months. Using the generalised pigeonhole principle, to be sure some month has at least 3 students we need $N>2\times12=24$, so $N=25$.

With 24 students, two in each month is possible, but with 25 students at least three share a month.

A function $f$ from a set $A$ to a set $B$ is a rule that assigns to each element $a\in A$ exactly one element $f(a)\in B$. Equivalently, it is a relation $f\subseteq A\times B$ in which every $a\in A$ appears as the first coordinate of exactly one ordered pair.

Inverse of $f$. $f(x)=4x-3$ is one-to-one and onto. Put $y=4x-3$, so $x=\dfrac{y+3}{4}$. Hence $f^{-1}(y)=\frac{y+3}{4}.$

Composition $g\circ f$. $(g\circ f)(x)=g(f(x))=g(4x-3)=6(4x-3)-2=24x-20.$

Binomial theorem. For a positive integer $n$, $(x+y)^n=\sum_{k=0}^{n}C(n,k)\,x^{n-k}y^{k}=C(n,0)x^n+C(n,1)x^{n-1}y+\dots+C(n,n)y^n .$

Binomial coefficients. The numbers $C(n,k)=\dfrac{n!}{k!(n-k)!}$, $k=0,1,\dots,n$, which appear as the coefficients in this expansion.

7th term of $\left(x+\dfrac1x\right)^{10}$. The $(k+1)$-th term is $C(10,k)x^{10-k}x^{-k}$. For the 7th term $k=6$: $T_7=C(10,6)\,x^{4}\left(\frac1x\right)^{6}=210\,x^{-2}=\frac{210}{x^{2}}.$

A full binary tree is a rooted tree in which every internal vertex has exactly two children.

Let $i$ be the number of internal vertices and $t$ the number of pendant (leaf) vertices, so $n=i+t$.

$n$ is odd. Every vertex except the root is the child of exactly one internal vertex, and each internal vertex has exactly 2 children. So $n-1=2i\quad\Rightarrow\quad n=2i+1,$ which is odd.

Number of pendant vertices. From $n=2i+1$ we get $i=\dfrac{n-1}{2}$, so $t=n-i=n-\frac{n-1}{2}=\frac{n+1}{2}=\tfrac12(n+1). \qquad\blacksquare$

A set is countable if it is finite or can be put in one-to-one correspondence with the set $\mathbb{Z}^+$ of positive integers.

Let $O=\{1,3,5,\dots\}$ and define $f:\mathbb{Z}^+\to O$ by $f(n)=2n-1$.

• One-to-one: $2m-1=2n-1\Rightarrow m=n$.
• Onto: every odd positive integer $k$ equals $f\!\left(\frac{k+1}{2}\right)$ with $\frac{k+1}{2}\in\mathbb{Z}^+$.

So $f$ is a bijection and $O$ is countably infinite, i.e. countable.

An edge is a bridge exactly when it lies on no cycle. If every edge of $G$ is a bridge, then $G$ has no cycle at all, so $G$ is a forest (each component is a tree). If $G$ is also connected, it is a tree.

Equivalence relation. A relation on a set that is reflexive, symmetric and transitive.

$R=\{(x,y):x\equiv y \pmod 4\}$ on $A=\{1,\dots,15\}$, i.e. $4\mid(x-y)$.

• Reflexive: $x-x=0$ is divisible by 4, so $(x,x)\in R$.
• Symmetric: if $4\mid(x-y)$ then $4\mid(y-x)$, so $(y,x)\in R$.
• Transitive: if $4\mid(x-y)$ and $4\mid(y-z)$ then $4\mid(x-z)$ (their sum), so $(x,z)\in R$.

So $R$ is an equivalence relation.

Partition (equivalence classes by remainder mod 4): $[1]=\{1,5,9,13\},\quad [2]=\{2,6,10,14\},\quad [3]=\{3,7,11,15\},\quad [4]=\{4,8,12\}.$ The partition is $\{\{1,5,9,13\},\{2,6,10,14\},\{3,7,11,15\},\{4,8,12\}\}$.

Bipartite graph. A graph whose vertex set can be split into two disjoint sets $V_1,V_2$ such that every edge joins a vertex of $V_1$ to a vertex of $V_2$. If every vertex of $V_1$ is joined to every vertex of $V_2$, with $|V_1|=m$ and $|V_2|=n$, it is the complete bipartite graph $K_{m,n}$.

Order. The vertex set is $V_1\cup V_2$ with $V_1\cap V_2=\emptyset$, so the order is $m+n$.

Size. Each of the $m$ vertices of $V_1$ is adjacent to all $n$ vertices of $V_2$ and to no vertex of $V_1$. Every edge has exactly one end in $V_1$, so the number of edges is the sum of the degrees of $V_1$: $|E|=m\cdot n .$ (Check: the degree sum is $mn+nm=2mn=2|E|$.) Hence the size is $mn$ and the order is $m+n$. $\blacksquare$

Let $G$ be $r$-regular with $n$ vertices and $e$ edges, where $r$ is odd. By the handshaking lemma,

$\sum_{v}\deg(v) = rn = 2e,$

which is even. Since $r$ is odd, $rn$ can be even only if $n$ is even. Hence $G$ has an even number of vertices. $\blacksquare$

In a full binary tree every internal vertex has exactly two children. Let $i$ be the number of internal vertices and $t$ the number of pendant vertices (leaves), so $n=i+t$.

Every vertex except the root is the child of exactly one internal vertex, so $n-1=2i$, giving $i=\frac{n-1}{2}$. Then

$t=n-i=n-\frac{n-1}{2}=\frac{n+1}{2}.\ \blacksquare$

$K_{8,9}$ has $8+9=17$ vertices. Each of the $8$ vertices in the first part is joined to each of the $9$ in the second, so there are $8\times 9=72$ edges.

If every edge of a simple graph $G$ is a bridge, then no edge lies on a cycle, so $G$ has no cycles. Hence $G$ is a forest, and if it is connected it is a tree.

Definition. If $f:A\to B$ and $g:B\to C$, the composition of $f$ and $g$ is the function $g\circ f:A\to C$ given by $(g\circ f)(x)=g(f(x))$. Similarly, $f\circ g$ means $(f\circ g)(x)=f(g(x))$, defined when the range of $g$ lies in the domain of $f$.

Here $f(x)=4x-3$ and $g(x)=5x$ on $\mathbb{R}$, so both compositions are defined.

$(f\circ g)(x)=f(g(x))=4(5x)-3=20x-3,$

$(g\circ f)(x)=g(f(x))=5(4x-3)=20x-15.$

Since $20x-3\ne 20x-15$, $f\circ g\ne g\circ f$.

Tree. A tree is a connected graph with no cycles. Examples: a path $P_n$; the star $K_{1,n}$; a single vertex (the trivial tree).

Theorem. A tree with $n\ge 2$ vertices has at least two vertices of degree $1$.

Proof. Let $T$ be a tree with $n\ge2$ vertices. It is connected, so it has at least one edge. Take a longest path $P=v_0v_1\cdots v_k$ in $T$, where $k\ge1$.

Suppose $v_0$ had a neighbour $w$ other than $v_1$. If $w$ is on $P$, then $w=v_j$ with $j\ge2$ and $v_0v_1\cdots v_jv_0$ is 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 $v_0$ has only the neighbour $v_1$, hence $\deg(v_0)=1$.