Mathematical Foundation for Computer Science

Planar graph. A graph is planar if it can be drawn in the plane so that no two edges cross except at their end vertices. Such a drawing divides the plane into regions called faces.

Euler graph. A connected graph is an Euler graph if it has an Euler circuit, that is, a closed walk that uses every edge exactly once. A connected graph is Eulerian if and only if every vertex has even degree.

Numerical part. The degrees are $2, 2, 2, 3, 3, 3, 4, 4, 5$ and $v = 9$.

Sum of degrees:

$2+2+2+3+3+3+4+4+5 = 28$

By the handshaking theorem, $2e = 28$, so

$e = 14$

By Euler's formula for a connected planar graph, $v - e + f = 2$:

$9 - 14 + f = 2 \;\Rightarrow\; f = 7$

Number of edges = 14 and number of faces = 7.

$a_n = 2a_{n-1} - a_{n-2},\qquad a_0 = 3,\ a_1 = 6$

Characteristic equation:

$r^2 - 2r + 1 = 0 \;\Rightarrow\; (r-1)^2 = 0 \;\Rightarrow\; r = 1 \text{ (repeated root)}$

General solution:

$a_n = (A + Bn)\,1^n = A + Bn$

Using the initial conditions:

• $a_0 = A = 3$.
• $a_1 = A + B = 6 \Rightarrow B = 3$.

Solution:

$a_n = 3 + 3n = 3(n+1)$

Check: $a_2 = 2(6) - 3 = 9 = 3(3)$.

Hamiltonian path and circuit. A Hamiltonian path in a graph is a simple path that visits every vertex exactly once. A Hamiltonian circuit (cycle) is a simple cycle that passes through every vertex exactly once and returns to the starting vertex. A graph that has a Hamiltonian circuit is called a Hamilton (Hamiltonian) graph. The idea is named after Sir William Rowan Hamilton, who introduced it through the "icosian game".

Examples. The cycle $C_n$, the complete graph $K_n$ ($n \ge 3$) and the cube $Q_3$ are Hamiltonian. The complete bipartite graph $K_{2,3}$ is not.

Sufficient conditions (a graph with $n \ge 3$ vertices):

• Dirac's theorem: if $\deg(v) \ge n/2$ for every vertex $v$, the graph is Hamiltonian.
• Ore's theorem: if $\deg(u) + \deg(v) \ge n$ for every pair of non-adjacent vertices $u, v$, the graph is Hamiltonian.

Necessary conditions: every vertex must have degree at least 2, and the graph must be connected with no cut vertex. If a vertex of degree 2 exists, both its edges must be in the circuit.

Comparison with Euler circuit. An Euler circuit uses every edge once and has a simple degree test (all degrees even). For a Hamiltonian circuit, which uses every vertex once, no simple necessary and sufficient test is known; deciding it is NP-complete.

Application: the travelling salesman problem asks for the cheapest Hamiltonian circuit in a weighted graph.

$a_n = 5a_{n-1} - 6a_{n-2} + 42\cdot 4^n,\qquad a_0 = 56,\ a_1 = 278$

Homogeneous part. $r^2 - 5r + 6 = 0 \Rightarrow (r-2)(r-3) = 0$, so $r = 2, 3$ and

$a_n^{(h)} = A\,2^n + B\,3^n$

Particular solution. Since $4$ is not a characteristic root, try $a_n^{(p)} = C\cdot 4^n$. Substituting:

$C4^n = 5C4^{n-1} - 6C4^{n-2} + 42\cdot 4^n$

Divide by $4^{n-2}$:

$16C = 20C - 6C + 42\cdot 16 \;\Rightarrow\; 16C = 14C + 672 \;\Rightarrow\; C = 336$

General solution:

$a_n = A\,2^n + B\,3^n + 336\cdot 4^n$

Initial conditions:

• $n=0$: $A + B + 336 = 56 \Rightarrow A + B = -280$.
• $n=1$: $2A + 3B + 1344 = 278 \Rightarrow 2A + 3B = -1066$.

Subtracting twice the first equation from the second: $B = -1066 + 560 = -506$, so $A = -280 + 506 = 226$.

Solution:

$a_n = 226\cdot 2^n - 506\cdot 3^n + 336\cdot 4^n$

Check: $a_1 = 452 - 1518 + 1344 = 278$. ✓

DFA. A Deterministic Finite Automaton is a 5-tuple $M = (Q, \Sigma, \delta, q_0, F)$ where $Q$ is a finite set of states, $\Sigma$ the input alphabet, $\delta : Q \times \Sigma \to Q$ the transition function (exactly one next state for every state and symbol), $q_0 \in Q$ the start state, and $F \subseteq Q$ the set of accepting (final) states.

DFA for $L = \{w \in \{a,b\}^* : w \text{ starts with } abb\}$.

States: $Q = \{q_0, q_1, q_2, q_3, q_d\}$, start state $q_0$, final state $F = \{q_3\}$, $q_d$ a dead (trap) state.

Working: $q_0 \xrightarrow{a} q_1 \xrightarrow{b} q_2 \xrightarrow{b} q_3$; once $abb$ has been read the machine stays in $q_3$ whatever follows. Any other beginning (for example $b\ldots$, $aa\ldots$, $aba\ldots$) goes to the dead state, which is never accepted.

Example: $abbab$ ends in $q_3$ (accepted); $abab$ ends in $q_d$ (rejected).

$a_n - 6a_{n-1} + 8a_{n-2} = 3,\qquad a_0 = 10,\ a_1 = 25$

Homogeneous part. $r^2 - 6r + 8 = 0 \Rightarrow (r-2)(r-4) = 0$, so

$a_n^{(h)} = A\,2^n + B\,4^n$

Particular solution. The right-hand side is a constant and $1$ is not a characteristic root, so try $a_n^{(p)} = C$:

$C - 6C + 8C = 3 \;\Rightarrow\; 3C = 3 \;\Rightarrow\; C = 1$

General solution:

$a_n = A\,2^n + B\,4^n + 1$

Initial conditions:

• $n=0$: $A + B + 1 = 10 \Rightarrow A + B = 9$.
• $n=1$: $2A + 4B + 1 = 25 \Rightarrow A + 2B = 12$.

Subtracting: $B = 3$, then $A = 6$.

Solution:

$a_n = 6\cdot 2^n + 3\cdot 4^n + 1$

Check: $a_1 = 12 + 12 + 1 = 25$ and $a_2 = 24 + 48 + 1 = 73 = 6(25) - 8(10) + 3$. ✓

DFA. A Deterministic Finite Automaton is a 5-tuple $M = (Q, \Sigma, \delta, q_0, F)$: $Q$ a finite set of states, $\Sigma$ the input alphabet, $\delta : Q \times \Sigma \to Q$ the transition function (exactly one move for each state and symbol), $q_0$ the start state and $F \subseteq Q$ the set of final (accepting) states. A string is accepted if the DFA is in a final state after reading it completely.

DFA for $L = \{w \in \{a,b\}^* : w \text{ ends with } bb\}$.

States: $q_0$ (start; the last symbol is not $b$, or nothing read), $q_1$ (the string ends in exactly one $b$), $q_2$ (the string ends in $bb$; the final state).

Formally, $Q = \{q_0, q_1, q_2\}$, $\Sigma = \{a, b\}$, $F = \{q_2\}$.

Working: an $a$ always breaks a run of $b$s and returns to $q_0$; one $b$ moves $q_0 \to q_1$; a second consecutive $b$ moves $q_1 \to q_2$; further $b$s keep the machine in $q_2$.

Example: $abb$ goes $q_0 \to q_0 \to q_1 \to q_2$ (accepted); $abba$ goes back to $q_0$ (rejected); $bab$ ends in $q_1$ (rejected).

A regular expression (RE) is converted to a DFA in two stages: RE $\to$ $\varepsilon$-NFA (Thompson's construction), then $\varepsilon$-NFA $\to$ DFA (subset construction).

Step 1: RE to $\varepsilon$-NFA (Thompson's construction). Build small NFAs for the basic parts and combine them:

• Symbol $a$: two states $s \xrightarrow{a} f$. The empty string $\varepsilon$: $s \xrightarrow{\varepsilon} f$.
• Union $R_1 + R_2$: a new start state with $\varepsilon$-moves to the starts of both NFAs, and $\varepsilon$-moves from both finals to a new final state.
• Concatenation $R_1R_2$: an $\varepsilon$-move from the final state of $R_1$ to the start state of $R_2$.
• Closure $R^*$: a new start and final state, with $\varepsilon$-moves start $\to$ start of $R$, final of $R$ $\to$ final of $R$-NFA's new final, final of $R$ $\to$ start of $R$ (repeat), and start $\to$ new final (zero repetitions).

Step 2: $\varepsilon$-NFA to DFA (subset construction).

1. Compute the $\varepsilon$-closure of the NFA start state; this is the DFA start state.
2. For each DFA state $S$ (a set of NFA states) and each input symbol $a$, compute $\varepsilon\text{-closure}(\delta(S,a))$; this set is a DFA state.
3. Repeat until no new sets appear.
4. Any DFA state that contains an NFA final state is a final state.

Example: $a(a+b)^*b$. Thompson's construction gives an $\varepsilon$-NFA; after removing the $\varepsilon$-moves it reduces to the following NFA:

NFA: $q_0 \xrightarrow{a} q_1$; $q_1 \xrightarrow{a,b} q_1$; $q_1 \xrightarrow{b} q_2$, final state $q_2$.

Subset construction:

Start state $A$, final state $C$. The resulting DFA accepts exactly the strings that start with $a$ and end with $b$, which is the language of $a(a+b)^*b$. If needed, the DFA can be minimised by merging equivalent states.

Regular expression (RE). A regular expression is an algebraic notation describing a regular language, built from symbols of $\Sigma$, $\varepsilon$ and $\emptyset$ using union ($+$ or $|$), concatenation, and Kleene closure ($*$). For example, $(a+b)^*abb$ describes all strings over $\{a,b\}$ ending in $abb$.

Applications.

• Lexical analysis: compilers use REs to define tokens (identifiers, numbers, keywords), which are converted into DFAs by tools such as Lex/Flex.
• Pattern matching and search: grep, sed, text editors and IDEs find and replace text patterns.
• Input validation: checking email addresses, phone numbers, passwords and dates in forms.
• Data extraction and web scraping: pulling structured fields from logs and documents.
• Network and security tools: intrusion detection and packet filtering match patterns in traffic.
• Specification of protocols and hardware: describing the language accepted by simple controllers and finite-state machines.

Converting a DFA to a regular expression (state elimination method).

1. Add a new start state with an $\varepsilon$-edge to the old start state, and a new single final state with $\varepsilon$-edges from every old final state.
2. Label every edge with an RE (merge parallel edges with $+$).
3. Eliminate the remaining states one at a time. To remove state $s$, for every pair of states $p$ and $q$ with edges $p\xrightarrow{R_1}s$, $s\xrightarrow{R_2}q$, and a self-loop $s\xrightarrow{S}s$, add the edge $p\xrightarrow{R_1S^*R_2}q$ (union it with any existing $p\to q$ edge).
4. When only the new start and final states remain, the label on the edge between them is the RE of the DFA.

Example. DFA with states $q_0$ (start), $q_1$ (final): $q_0\xrightarrow{a}q_1$, $q_0\xrightarrow{b}q_0$, $q_1\xrightarrow{a}q_1$, $q_1\xrightarrow{b}q_0$. Eliminating $q_1$ (loop $a$, in-edge $a$, out-edge $b$ to $q_0$) gives a loop on $q_0$ labelled $b + aa^*b$, and the path to the final state is $a\,a^*$. Hence

$R=(b+aa^*b)^*\,aa^*,$

which is equivalent to $(a+b)^*a$: all strings ending in $a$.

Another method is Arden's theorem: write state equations $q_i = \sum q_j a + \varepsilon$ (for the start) and solve using $R = Q + RP \Rightarrow R = QP^*$.

Graph theory is the branch of mathematics that studies graphs. A graph $G = (V, E)$ consists of a non-empty set $V$ of vertices (nodes) and a set $E$ of edges joining pairs of vertices. Graphs model pairwise relations between objects, and graph theory studies their properties such as paths, cycles, connectivity, colouring, trees and planarity.

Applications in computer science:

1. Computer networks. Computers or routers are vertices and links are edges. Shortest-path algorithms (Dijkstra, Bellman-Ford) are used for routing, and spanning trees (Prim, Kruskal) for cheap network design and loop-free switching.
2. World Wide Web and search engines. Web pages are vertices and hyperlinks are directed edges. Crawlers traverse this graph by BFS/DFS, and PageRank ranks pages using the link structure.
3. Social networks. People are vertices and friendships are edges. Graph algorithms find communities, influencers and friend suggestions.
4. Compiler design and operating systems. Control-flow graphs and data-flow graphs are used in optimisation. Register allocation is done by graph colouring. Directed graphs of resource allocation are used to detect deadlock (cycles).
5. Databases and data structures. Trees, heaps and tries are special graphs. Entity relationships and dependency graphs are modelled with graphs.
6. Scheduling and resource allocation. Graph colouring is used for timetabling and frequency assignment, and topological sorting for ordering tasks with dependencies.
7. Artificial intelligence. State-space search (BFS, DFS, A*), decision trees and Bayesian networks use graphs.
8. Circuit design (VLSI). Planar graphs are used to lay out circuits without crossing wires.
9. Software engineering. Call graphs, module dependency graphs and finite-state machines.

Dijkstra's algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph with non-negative edge weights.

1. Set $d(\text{source}) = 0$ and $d(v) = \infty$ for every other vertex. Let $S = \emptyset$ (the set of finished vertices).
2. Pick the vertex $u \notin S$ with the smallest $d(u)$ and add it to $S$.
3. For every neighbour $v$ of $u$ with $v \notin S$: 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 the destination is in $S$ (or all vertices are in $S$).
5. Trace the predecessors back from the destination to get the path.

Worked example. Consider the weighted graph with edges $A\text{-}B = 4$, $A\text{-}C = 2$, $B\text{-}C = 1$, $B\text{-}D = 5$, $C\text{-}D = 8$, $C\text{-}E = 10$, $D\text{-}E = 2$.

Shortest path: $A \to C \to B \to D \to E$, with length $2 + 1 + 5 + 2 = 10$.

Example: Hamiltonian but not Eulerian (5 vertices). Take the 5-cycle $v_1v_2v_3v_4v_5$ and add the chord $v_1v_3$.

• Hamiltonian: $v_1 \to v_2 \to v_3 \to v_4 \to v_5 \to v_1$ visits all five vertices once.
• Not Eulerian: $\deg(v_1) = 3$ and $\deg(v_3) = 3$ are odd, so no Euler circuit exists.

Tautology. A compound proposition that is true for every assignment of truth values to its variables, for example $p \vee \sim p$.

Contradiction. A compound proposition that is false for every assignment of truth values, for example $p \wedge \sim p$.

Logical equivalence. Two propositions $A$ and $B$ are logically equivalent, written $A \equiv B$, if $A \leftrightarrow B$ is a tautology, i.e. they have the same truth value in every row of the truth table.

Claim. $p \to q \equiv \sim q \to \sim p$.

The last two columns are identical in every row, so $p \to q \equiv \sim q \to \sim p$: an implication and its contrapositive are logically equivalent.

Algebraic check. $\sim q \to \sim p \equiv \sim(\sim q) \vee \sim p \equiv q \vee \sim p \equiv \sim p \vee q \equiv p \to q$.

Principle of mathematical induction. Let $P(n)$ be a statement about the integer $n \ge n_0$. If

1. Basis step: $P(n_0)$ is true, and
2. Inductive step: for every $k \ge n_0$, $P(k) \Rightarrow P(k+1)$,

then $P(n)$ is true for all integers $n \ge n_0$.

Proof. Let $P(n)$: $1 + 3 + 5 + \cdots + (2n-1) = n^2$.

Basis step ($n = 1$). LHS $= 1$ and RHS $= 1^2 = 1$. So $P(1)$ is true.

Inductive step. Assume $P(k)$ is true for some $k \ge 1$:

$1 + 3 + 5 + \cdots + (2k-1) = k^2$

Add the next term $2(k+1) - 1 = 2k+1$ to both sides:

$1 + 3 + \cdots + (2k-1) + (2k+1) = k^2 + 2k + 1 = (k+1)^2$

This is exactly $P(k+1)$. Hence $P(k) \Rightarrow P(k+1)$.

By the principle of mathematical induction, $1 + 3 + 5 + \cdots + (2n-1) = n^2$ for all $n \ge 1$. $\blacksquare$

Let $p$: it rains; $w$: the ground is wet; $q$: the picnic is held; $h$: I have a good time.

Premises: $p \to w$, $\ \sim p \to q$, $\ q \to h$.

Conclusion: $\sim w \to h$.

The conclusion follows from the premises by valid rules of inference, so the argument is valid.

Difference between direct and indirect proof

Theorem. $\sqrt{2}$ is irrational.

Proof (by contradiction). Suppose $\sqrt{2}$ is rational. Then $\sqrt{2} = \dfrac{a}{b}$ with integers $a, b$, $b \ne 0$, and $a, b$ have no common factor (the fraction is in lowest terms).

Squaring gives $2 = \dfrac{a^2}{b^2}$, so

$a^2 = 2b^2$

Thus $a^2$ is even, which means $a$ is even (if $a$ were odd, $a^2$ would be odd). Write $a = 2k$. Then

$4k^2 = 2b^2 \;\Rightarrow\; b^2 = 2k^2$

So $b^2$ is even, and hence $b$ is even.

Now both $a$ and $b$ are even, so they have the common factor $2$. This contradicts the assumption that $\dfrac{a}{b}$ is in lowest terms.

Therefore the assumption is false, and $\sqrt{2}$ is irrational. $\blacksquare$

Finite State Machine (FSM). A finite state machine is an abstract model of computation with a finite number of states. At any time it is in exactly one state, and it moves from state to state on input symbols according to a transition function. It is used to model digital circuits, protocols, lexical analysers and control systems.

Types:

1. FSM with output (Mealy/Moore machine). $M = (S, I, O, f, g, s_0)$: $S$ states, $I$ input alphabet, $O$ output alphabet, $f: S \times I \to S$ the next-state function, $g$ the output function (depending on state and input for Mealy, on state only for Moore), and $s_0$ the initial state.
2. FSM without output (finite automaton, DFA/NFA). $M = (Q, \Sigma, \delta, q_0, F)$ with a set $F$ of final states. It accepts a string if it ends in a final state. The accepted strings form a regular language.

Example 1 (Mealy machine: parity / unit delay). A machine with states $s_0, s_1$ that outputs $1$ when the input bit differs from the previous one.

For input $0110$ from $s_0$, the output is $0\,1\,0\,1$.

Example 2 (DFA). A DFA accepting binary strings with an even number of 1s: states $E$ (start and final) and $O$; on $0$ stay in the same state, on $1$ switch between $E$ and $O$.

Example 3 (vending machine). States record the amount inserted (0, 5, 10); inputs are coins; the output is "release item" once the total reaches 15.

An FSM is drawn as a state diagram (circles for states, labelled arrows for transitions) or written as a state table.

Grammar. A formal grammar describes how to generate the strings of a language. It is defined as a 4-tuple

$G = (V, T, P, S)$

• $V$: finite set of variables (non-terminals).
• $T$: finite set of terminals (the alphabet of the language), with $V \cap T = \emptyset$.
• $P$: finite set of production rules of the form $\alpha \to \beta$.
• $S \in V$: the start symbol.

The language generated is $L(G) = \{w \in T^* : S \Rightarrow^* w\}$, the set of terminal strings derivable from $S$.

Example. $G = (\{S\}, \{a, b\}, P, S)$ with $P: S \to aSb \mid ab$ generates $\{a^n b^n : n \ge 1\}$. A derivation is $S \Rightarrow aSb \Rightarrow aabb$.

Chomsky hierarchy:

Each type is a proper subset of the one above it. Grammars are used to define programming-language syntax and in compiler design.

Predicate. A predicate is a statement containing one or more variables that becomes a proposition when values are assigned to the variables, for example $P(x)$: "$x > 3$". $P(5)$ is true and $P(1)$ is false. The set of values allowed for $x$ is the domain (universe of discourse).

Quantifiers. Quantifiers state for how many values of the variable the predicate holds.

1. Universal quantifier $\forall$ ("for all"). $\forall x\, P(x)$ is true if $P(x)$ is true for every $x$ in the domain, and false if there is at least one counterexample.
2. Existential quantifier $\exists$ ("there exists"). $\exists x\, P(x)$ is true if $P(x)$ is true for at least one $x$ in the domain, and false if $P(x)$ is false for every $x$.

Negation (generalised De Morgan laws):

$\sim\forall x\, P(x) \equiv \exists x\, \sim P(x),\qquad \sim\exists x\, P(x) \equiv \forall x\, \sim P(x)$

Examples. Domain: real numbers. $\forall x\,(x^2 \ge 0)$ is true. $\exists x\,(x^2 = 2)$ is true. $\forall x\,(x > 0)$ is false.

Translation. "All students are clever" is $\forall x\,(S(x) \to C(x))$; "Some student is clever" is $\exists x\,(S(x) \wedge C(x))$.

Quantified predicates are the basis of predicate logic, used in specifications, databases (SQL) and automated reasoning.

Path matrix (reachability matrix). For a directed graph $G$ with $n$ vertices $v_1, \dots, v_n$, the path matrix $P = [p_{ij}]$ is the $n \times n$ Boolean matrix with

$p_{ij} = \begin{cases} 1 & \text{if there is a path from } v_i \text{ to } v_j \\ 0 & \text{otherwise} \end{cases}$

It tells which vertices can be reached from which, whatever the path length.

Computing from the adjacency matrix $A$. A path in an $n$-vertex graph has length at most $n$, so

$B_n = A + A^2 + A^3 + \cdots + A^n$

and $p_{ij} = 1$ if the entry $(B_n)_{ij} \ne 0$, else $0$. Equivalently, $P = A \vee A^{(2)} \vee \cdots \vee A^{(n)}$ using Boolean matrix products.

Warshall's algorithm computes it more efficiently. Start with $P^{(0)} = A$ and for $k = 1, \dots, n$ set

$p^{(k)}_{ij} = p^{(k-1)}_{ij} \vee \left(p^{(k-1)}_{ik} \wedge p^{(k-1)}_{kj}\right)$

The final matrix $P^{(n)}$ is the path matrix. It takes $O(n^3)$ time.

Uses. Testing whether a graph is strongly connected (all entries of $P$ are 1), finding the transitive closure of a relation, and detecting cycles (some $p_{ii} = 1$).

Pseudograph. A graph in which both multiple edges (parallel edges) and loops (an edge joining a vertex to itself) are allowed. Example: vertices $a, b$ with two edges between $a$ and $b$ and a loop at $a$.

Directed graph (digraph). A graph $G = (V, E)$ in which each edge is an ordered pair $(u, v)$ of vertices, drawn as an arrow from $u$ (initial vertex) to $v$ (terminal vertex). Example: $V = \{1, 2, 3\}$, $E = \{(1,2), (2,3), (3,1)\}$ is a directed triangle.

Wheel $W_n$. Take the cycle $C_n$ and add one new vertex (the hub) joined to every vertex of the cycle. Example: $W_4$ has 5 vertices (a 4-cycle plus a hub) and $4 + 4 = 8$ edges.

Tree. A connected undirected graph with no cycles. A tree with $n$ vertices has exactly $n-1$ edges, and there is a unique path between any two vertices. Example: a path $a - b - c - d$, or a star with one centre joined to three leaves.

Number of edges of $K_n$. In the complete graph $K_n$ every pair of distinct vertices is joined by exactly one edge, so the number of edges equals the number of ways to choose 2 vertices from $n$:

$|E| = \binom{n}{2} = \frac{n(n-1)}{2}$

Alternatively, each vertex has degree $n-1$, so by the handshaking theorem $2|E| = n(n-1)$, giving $|E| = \dfrac{n(n-1)}{2}$. $\blacksquare$

Take the graph with vertices $V_1, \dots, V_5$ and edges $e_1 = V_1V_2,\ e_2 = V_1V_3,\ e_3 = V_2V_3,\ e_4 = V_2V_4,\ e_5 = V_3V_4,\ e_6 = V_3V_5,\ e_7 = V_4V_5,\ e_8 = V_1V_5$.

Adjacency matrix. $A = [a_{ij}]$ is $5 \times 5$ with $a_{ij} = 1$ if $V_i$ and $V_j$ are joined by an edge (the count of edges if parallel edges exist), else $0$. For an undirected graph it is symmetric.

$A = \begin{array}{c|ccccc} & V_1 & V_2 & V_3 & V_4 & V_5 \\ \hline V_1 & 0 & 1 & 1 & 0 & 1 \\ V_2 & 1 & 0 & 1 & 1 & 0 \\ V_3 & 1 & 1 & 0 & 1 & 1 \\ V_4 & 0 & 1 & 1 & 0 & 1 \\ V_5 & 1 & 0 & 1 & 1 & 0 \end{array}$

Row sums give the degrees: $3, 3, 4, 3, 3$.

Incidence matrix. $B = [b_{ij}]$ is $5 \times 8$ (vertices by edges) with $b_{ij} = 1$ if vertex $V_i$ is an end of edge $e_j$, else $0$.

$B = \begin{array}{c|cccccccc} & e_1 & e_2 & e_3 & e_4 & e_5 & e_6 & e_7 & e_8 \\ \hline V_1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\ V_2 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ V_3 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 0 \\ V_4 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 \\ V_5 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \end{array}$

Each column has exactly two 1s (every edge has two end vertices), and each row sum equals the degree of the vertex.

Consider the weighted graph with edges $ab = 4,\ ac = 2,\ bc = 1,\ bd = 5,\ cd = 8,\ ce = 10,\ de = 2,\ dz = 6,\ ez = 3$.

Dijkstra's algorithm. Set $d(a) = 0$ and all other labels $\infty$. Repeatedly fix the unfixed vertex with the smallest label and relax the labels of its neighbours.

Labels at each step: after fixing $c$, $b = \min(4, 2+1) = 3$, $d = 2+8 = 10$, $e = 2+10 = 12$; after fixing $b$, $d = \min(10, 3+5) = 8$; after fixing $d$, $e = \min(12, 8+2) = 10$ and $z = 8+6 = 14$; after fixing $e$, $z = \min(14, 10+3) = 13$.

Tracing predecessors back from $z$: $z \leftarrow e \leftarrow d \leftarrow b \leftarrow c \leftarrow a$.

Shortest path: $a \to c \to b \to d \to e \to z$, of length $2 + 1 + 5 + 2 + 3 = 13$. These edges are the ones highlighted in the graph.

Let $p$: I work hard; $q$: I get a job; $r$: I will be happy.

Premises: $p \to q$, $\ q \to r$, $\ \sim r$.

Conclusion: $\sim q \vee \sim p$.

Hence the argument is valid.