Fault-tolerance property of Complete Graphs

Let K_n denote a complete graph of n vertices, and deg_G (v) denote the degree of a vertex v in G.

Lemma 1

The graph G = K_n - F has a hamiltonian cycle for every set of edges F in K_n with $\vert F\vert \le n - 3$.

Proof. $\;$ Let x and y be two different nodes of K_n. The Ore's Theorem [7] states that a graph H of m nodes has a hamiltonian cycle if $deg_H(x) + deg_H(y) \ge m$ for every pair of non-adjacent vertices x, y in H. Since $\deg_G(x)+ \deg_G(y) \ge 2(n-2) - (n-4) \ge n$ for every pair of non-adjacent vertices x, y in G, it follows that G has a hamiltonian cycle. Hence the lemma follows. $\Box$

Applying Lemma 1, we can obtain the following Corollary.

Corollary 1

The graph K_n- F has a hamiltonian path for every set of edges F in K_n with $\vert F\vert \le n-2$.

Let $r \ge 2$ be an integer. A graph G is said to be r-HP if there exists $V' \subseteq V(G)$ with |V'|=r such that every pair of nodes in V' can be joined by a hamiltonian path of G.

Theorem 1

  The graph K_n - F is (n-f)-HP for every $F \subset (V \cup E)$ with $\vert F\vert= f \le n - 2$, where K_n = (V,E).

Proof. $\;$ We prove this theorem by induction on n. This statement can be easily verified for n = 3 and 4. Assume that the statement holds for all K_j with $3 \le j \le n-1$ and $n \ge 5$.

First, we consider that $\vert F \cap V\vert = i \gt 0$. Then the graph K_n - F is isomorphic to K_n-i - F^* for some $\vert F^*\vert \le f -i$. By induction hypotheses, the graph K_n-i-F^* is (n-f)-HP. Hence the graph K_n -F is (n-f)-HP.

Next, we consider that $F \subset E$. When |F| = n - 2, it follows from Corollary 1 that the graph K_n - F has a hamiltonian path. Thus K_n-F is 2-HP. Now consider that $F \subset E$ and $\vert F\vert \le n - 3$. Let H denote the sub-graph of K_n given by (V, F). Since $\sum_{v \in V} \deg_H(v) \le 2(n-3)$, there exists a vertex $v \in V$ with $deg_H(v) \le 1$. We distinguish the following two cases.

Case 1: there exists a node v with $\deg_H(v) = 0$.

In other words, all of the edges incident at v are not in F. Thus, the graph K_n - v - F is isomorphic to K_n-1 - F. By induction hypotheses, the graph K_n - v -F is (n-1-f)-HP. Therefore, there exists a subset $V' \subseteq V-\{v\}$ with |V'| = n-1-f such that every two distinct nodes $x, y \in V'$ can be joined by a hamiltonian path of K_n -v -F. Let P be a hamiltonian path of K_n- v -F joining x and y which is written as $\langle x, x' \rightarrow P' \rightarrow y \rangle$, where x' is a node adjacent to x and P' is a path from x' to y. Then $\langle x, v, x' \rightarrow P' \rightarrow y \rangle$ and $\langle v, x, x' \rightarrow P' \rightarrow y \rangle$ form two hamiltonian paths of K_n - F from x to y and from v to y, respectively. Since x and y are arbitrary nodes in V', there always exists a hamiltonian path of K_n - F joining every pair of nodes in $V' \cup \{v\}$. Thus, the graph K_n-F is (n-f)-HP.

Case 2: there exists a node v with $\deg_H(v) = 1$.

Since there is exactly one edge incident at v which is also in F, it follows that the graph K_n - v - F is isomorphic to the graph K_n-1 - F^* where |F^*| = f-1. By induction hypotheses, the graph K_n-v-F is (n-f)-HP. Thus, there exists a subset $X \subseteq V-\{v\}$ with |X|=n-f such that every two distinct nodes $x, y \in X$ can be joined by a hamiltonian path of K_n-v-F. Let P be a hamiltonian path of K_n -v-F joining x and y, which is written as $\langle x=z_0, z_1, \ldots, z_{n-2}=y \rangle$. Since $n \ge 5$, there exists z_j, $0 \le j \le n-3$, such that $(v, z_j) \notin F$ and $(v, z_{j+1}) \notin F$. Then $\langle x=z_0, z_1, \ldots, z_j, v, z_{j+1}, \ldots, z_{n-2}=y \rangle$ forms a hamiltonian path of K_n-F joining x and y. Hence every pair of nodes in X can be joined by a hamiltonian path of K_n - F. Thus, the graph K_n-F is (n-f)-HP, and the theorem is proved. $\Box$