# Binary Numeration System with Alternating Signed Digits and Its Graph Theoretical Relationship
## 4 Graphs Related to Fibonacci Numbers and the Related Numerical System  
In this chapter, we apply the previously introduced graph theory technique. The positional values of the binary system are the powers of two. Now, we start with the Zeckendorff numeral system [25; 26; 27; 28]. Its positional values are the Fibonacci numbers. Denote by \((F_{i})_{i=0}^{\infty}\) the Fibonacci sequence ([29] A000045) defined as \(F_{n}=F_{n-1}+F_{n-2}\) (\(n\geq 2\)) with \(F_{0}=0\) and \(F_{1}=1\). We refer to \(F_{2}<F_{3}<F_{4}<\cdots\) as the Fibonacci numbers. So, when we mention Fibonacci numbers, we mean elements of the Fibonacci sequence with indices at least 2. In analogy to the previously introduced \(\mathcal{G}\) graph, we define a new graph. Definition 2: Our graph \(\mathcal{F}\) has a vertex set consisting of natural numbers. We connect vertices \(u\) and \(v\) if \(u+v\) is a Fibonacci number. Specifically, \(0\) is adjacent to exactly the Fibonacci numbers. In the graph \(\mathcal{F}\), there will be loops. First, note that every third Fibonacci number is even. For the sake of completeness, we acknowledge this commonly known fact. Lemma 2: \(F_{n}\) _(for \(n\geq 2\)) is even if and only if \(n\) is divisible by 3._  
Proof: \(F_{2}=1,F_{3}=2,F_{4}=3\). We prove by induction that for every positive integer \(k\), \(F_{3k}\) is even, and \(F_{3k-1}\) and \(F_{3k+1}\) are odd. For the base case \(k=1\), this is known. We assume that for \(k=\ell\) the claim is true: \(F_{3\ell}\) is even, and \(F_{3\ell-1}\) and \(F_{3\ell+1}\) are odd. We need to prove that \(F_{3\ell+3}\) is even, and \(F_{3\ell+2}\) and \(F_{3\ell+4}\) are odd. This is straightforward from \(F_{3\ell+2}=F_{3\ell+1}+F_{3\ell}\), \(F_{3\ell+3}=F_{3\ell+2}+F_{3\ell+1}\), and \(F_{3\ell+4}=F_{3\ell+3}+F_{3\ell+2}\). If \(u=v=F_{3k}/2\), then \(u+v=F_{3k}\). Thus, \(uv\) forms an edge in \(\mathcal{F}\), creating a loop. The graph \(\mathcal{F}\) is not a tree, not only because of the loop edges but also because it contains many 4-cycles. Lemma 3: If \(u,v,u^{\prime},v^{\prime}\) are non-negative integers such that \(u+v=F_{k}\), \(u+u^{\prime}=F_{k+2}\), and \(v+v^{\prime}=F_{k+2}\), then \(u^{\prime}+v^{\prime}=F_{k+3}\). Specifically, \(u,v,u^{\prime},v^{\prime}\) form the vertices of a 4-cycle. Proof: We only need to check that \(u^{\prime}+v^{\prime}\) will be a Fibonacci number with the right index. \[u^{\prime}+v^{\prime} =u+u^{\prime}=(F_{k+2}-u)+(F_{k+2}-v)=F_{k+2}+F_{k+2}-(u+v)\] \[=F_{k+2}+(F_{k+1}+F_{k})-F_{k}=F_{k+2}+F_{k+1}=F_{k+3}.\]  
Thus, the statement is obvious. Definition 3: Let \(u(\leq F_{k})\) be a positive integer. Define \(v=F_{k}-u\), \(u^{\prime}=F_{k+2}-u\), \(v^{\prime}=F_{k+2}-v)\). The cycle \(C_{k}(u)\) in the graph \(F\) is formed by the edges \(uv\), \(uu^{\prime}\), \(vv^{\prime}\), and \(u^{\prime}v^{\prime}\). Note that the cycles \(C_{k}(u)\) and \(C_{k}(F_{k}-u)\) are the same; only the roles of \(u\) and \(v\) are exchanged. **Lemma 4**. : _The points of the \(C_{k}(0)=C_{k}(F_{k})\) cycle (\(u=0\), \(v=F_{k}\), \(v^{\prime}=F_{k+1}\), \(u^{\prime}=F_{k+2}\)) are connected by only one additional edge beside the edges of the cycle: \(uv^{\prime}\). If \(u\) is a positive integer that is not a Fibonacci number, then among the points of \(C_{k}(u)\), only the edges of the cycle are present._  
Proof. : The points of the \(C_{k}(0)\) cycle are: \(u=0\), \(v=F_{k}\), \(v^{\prime}=F_{k+1}\), \(u^{\prime}=F_{k+2}\). \(uv^{\prime}\) is obviously an edge since \(u+v^{\prime}\) is a Fibonacci number. \(u^{\prime}\) and \(v\) may be connected. Because \(F_{k+2}<u^{\prime}+v=F_{k}+F_{k+2}<F_{k+1}+F_{k+2}=F_{k+3}\), their sum lies between two consecutive Fibonacci numbers, meaning it cannot be a Fibonacci number. Let \(a\) be a positive integer: \(F_{\ell}<a<F_{\ell+1}\leq F_{k}\). The points of the \(C_{k}(a)\) cycle are: \(u=a\), \(v=F_{k}-a\), \(v^{\prime}=F_{k+1}+a\), \(u^{\prime}=F_{k+2}-a\). Assume that \(uv^{\prime}\) is an edge of \(\mathcal{F}\).