What method is used to find the number of Hamiltonian paths of a fan graph in this proof?

Question

Theorem: The fan graph f_n+2 can be decomposed into 4n+2 Hamiltonian paths.

Proof: Let f_n+2 be the fan graph with vertex set V: {z,v_1,v_2,..,v_n+1,v_n+2}. Consider the vertex z. We construct a path P_n+2: v_1,v_2,..,v_n+1,v_n+2 excluding the vertex z. Connect the vertex z to the vertex v_1 of P_n+2, we get a spanning path Q_1:z,v_1,v_2,..,v_n+1,v_n+2. Also, connect the vertex z to the vertex v_n+2 of P_n+2, we get a spanning path Q_2: v_1,v_2,..,v_n+1,v_n+2,z. Therefore, considering the vertex z, we get 2 spanning paths.

Consider the vertex v_1. We construct n+2 paths excluding the vertex v_1.

R_1: z,v_2,v_3,v_4,..,v_n,v_n+1,v_n+2

R_2: v_2,z,v_3,v_4,..,v_n,v_n+1,v_n+2

R_3: v_2,v_3,z,v_4,..,v_n,v_n+1,v_n+2
.

.

.

R_n: v_2,v_3,v_4,.., v_n,z,v_n+1,v_n+2

R_n+1: v_2,v_3,v_4,.., v_n,v_n+1,z,v_n+2

R_n+2: v_2,v_3,v_4,.., v_n,v_n+1,v_n+2,z

Connect the vertex v_1 to the starting vertex of each paths R_i, 1<= i <= n+2, we get n+2 spanning paths. But the spanning path R’_n+2: v_1,v_2,v_3,v_4,..,v_n,v_n+1,v_n+2,z is same as Q_2: v_1,v_2,..,v_n+1,v_n+2,z. So we get n+1 spanning paths.

Also, we construct n paths excluding the vertex v_1.

S_1: z,v_n+2,v_n+1,v_n,..,v_5,v_4,v_3,v_2

S_2: v_2,z,v_n+2,v_n+1,v_n,..,v_5,v_4,v_3

S_3: v_2,v_3,z,v_n+2,v_n+1,v_n,..,v_5,v_4 .

.

.

S_n-2: v_2,v_3,v_4,..,v_n-2,z,v_n+2,v_n+1,v_n,v_n-1

S_n-1: v_2, v_3,v_4,..,v_n-1,z,v_n+2,v_n+1,v_n

S_n: v_2,v_3,v_4,..,v_n-1,z,v_n+2,v_n+1

Connect the vertex v_1 to the starting vertex of each paths S_i, 1<= I <= n, we get n spanning paths. Therefore, considering the vertex v_1, we get 2n+1 spanning paths.

Proceeding like this we get a sequence of Hamiltonian paths, 2,2n+1,2,2,..,2,1. The number of Hamiltonian paths in

f_n+2 = (2+2n+1)+(2+2+..+2)(n-1)+1

= 2n+3+2(n-1)+1

= 2n+4+2n-2

= 4n+2

I saw this proof and I understand the idea of the proof. However, I don't know how or where some value came from. At first they constructed n+2 paths resulted to n+1 spanning paths. Next, they constructed n paths resulted to n paths. So n+1 + n = 2n+1, they got 2n+1 spanning paths. Where does the constructed number of paths n+2 and n came from?

And for this sequence of hamiltonian paths 2,2n+1,(2,2,..,2,1). I know that the 2 and 2n+1 came from the number got from the proof. How about the next sequence of number (2,2,..,2,1)?

Answer 1

I'm not surprised you are confused. That description is torturous. Even the way they are counting this seems unnecessarily confusing. Why $n+2$ and not just $n$?

Recall that $f_{n+2}$ is formed by taking a straight path graph $P_{n+2}$, which we can think of as $n+2$ vertices on a straight line, with the edges being the segments between adjacent vertices, and adding a new vertex $z$ off that line, then connecting it to each of the previous vertices. Based on how they describe the paths, I think they originally started doing an inductive proof based on the length of $P_{n+2}$, by removing an endpoint, and figuring out how it could be added back in to the Hamiltonian paths of $f_{n+1}$. But along the way, they realized that describing the new paths made the induction moot. Thus we have this quixotic description of the paths in terms of a removed $v_1$.

The only Hamiltonian path for $P = P_{n+2}$ is the path graph itself. $z$ gives us some alternatives. But we can only visit $z$ once, so at most two of its connecting paths can be traversed. The question becomes how can we adapt $P$ to pick up $z$? If we have a path that visits $z$ at some point then goes back down to $P$, if the path were to go down to a vertex with two unvisited neighbors on $P$, whichever way we left that vertex would cut off ever visiting the other neighbor, meaning the path would not be Hamiltonian. So if we want a Hamiltonian path, either $z$ connects to one or both of the two endpoints, or else it connects to two adjacent vertices of $P$. Which leaves us with four choices on how the path can go:

• The first choice is simply to connect $z$ to one of the endpoints of $P$ and call it done. Since there are two endpoints, there are two such paths. They call these $Q_1$ and $Q_2$. These are the only Hamiltonian paths to have $z$ as one of the endpoints.
• Second, we can start at $v_1$, travel right along $P$ to some $v_k, 1 \le k \le n+1$, then pop up to $z$, and back down to $v_{k+1}$, where the path continues along $P$ to $v_{n+2}$. These are the paths they call $R_k'$. Since there are $n+1$ choices for $k$, this gives $n+1$ paths.
• Third, we can start at $v_1$, proceed right to $v_k$, up to $z$, then back down to the other endpoint $v_{n+2}$, and follow the path left to end at $v_{k+1}$. If we allow $k = n+1$, then coming back down to $v_{n+2}$, there would no place to go, which would result in the same path as in the previous case. So this time we have to restrict $1 \le k \le n$, giving $n$ paths starting at $v_1$. On the other hand, this option treats $v_1$ and $v_{n+2}$ in different manners. So you get a different path if you reversed it, starting at $v_{n+2}$, travelling left to $v_{k+1}$, popping up to $z$, back down to $v_1$, then heading right to end at $v_k$. So this contributes $2n$ total Hamilton paths. This appears to be their paths $S_k$. Though I have no clue at all how they came up with a count of "$2n+1$".
• Finally, we can start at some $v_k, 2 \le k \le n$, travel left to $v_1$, up to $z$, back down to $v_{n+2}$ and left again to $v_{k+1}$. If $k = 1$ or $n+1$, this would repeat a path of the previous case, so those are excluded. There are $n-1$ possible paths. I don't see where this fits in their descriptions. I suppose that incomprehensible thing beginning with "Proceeding like this" was intended to count them. But if I were an educator grading this proof, I would have given it a failing grade.

Adding it all together we have $2+ n+1 + 2n + n-1 = 4n+2$ possible Hamilton paths in total.