Let be $G=\langle V,E\rangle$ undirected and connected 3-regular graph with 8 vertices. Prove that $G$ has Hamiltonian path.
I am trying to prove the above claim, however I don`t know how to develop more my idea.
let be $k$ the maximum length of path which is not circuit in G. if we show that $k=8$ we done.
let $P_1=\langle v_1, v_2,...,v_k\rangle$ be path which is not circuit with $k$ length. all the neighbors of $v_1$ and $v_k$ are in this path. since if they are not in this path we will get contradiction to the maximum of k.
There are two possible cases:
if $v_1$ and $v_k$ are neighbors: so $\forall i$ such that $2\leq i\leq k-1$ all neighbors of $v_i$ are in path. and again, if $v_i$ has a neighbor $u$ which is not in path so we will get a path bigger than maximum $k$ and again contradiction to maximum of $k$. Then, we can see that all vertices in $G$ are in this path since $G$ is connected then we get $k=$number of vertices in G$=8$. So in this case $k=8$ and even more we got Hamiltonian circuit.
if $v_1$ and $v_k$ and not neighbors then we know that in our $G$ graph we have 12 edges from Handshaking lemma and also we know that for sure 4 edges (2 from $v_1$ and 2 from $v_k$) that are not in Hamiltonian path.
But now I have no idea how I can show that $k=8$ since I don`t know how to connect $k$ to my proof.
Here's a proof that as long as the path's length $l$ is less than 8, you can augment it to a path of length $l+1$ until you reach length $8$.
given a path of length $l < 8$, we can show that unless the path's two endpoints are adjacent and so creating a cycle that can be easily augmented to a path of length $l+1$ the way you showed, one of the endpoints must have a neighbor not in the path, which again gives us an easy augmentation.
by contradiction: if neither of the path's endpoints has a neighbor not in the path and they aren't adjacent to one another, each of them must have two neighbors along the path in addition to their original successive path neighbors. since each of the path's middle vertices has already degree 2, they can each have only one more neighbor, forcing the additional neighbors of our endpoints to be four distinct vertices. this is trivially impossible for a path of length 3-5, for a path of length 6 that would create a 3 regular graph, disconnected from the two vertices not in the path of our assumed to be connected graph. for a path of length 7, that would leave us with only a single vertex in the path with degree 2 while the rest have degree 3, and a single vertex outside of our path which doesn't have 3 vertices with degree less than 3 to make connections with.