# Binary Numeration System with Alternating Signed Digits and Its Graph Theoretical Relationship
## 4 Graphs Related to Fibonacci Numbers and the Related Numerical System
Then, \(u+v^{\prime}\) is a Fibonacci number  
\[u+v^{\prime}=(F_{k}-v)+(F_{k+2}-v)=F_{k}+F_{k+2}-2v<F_{k}+F_{k+2}<F_{k+3};\]  
furthermore,  
\[u+v^{\prime}=F_{k}+F_{k+2}-2v>F_{k}+F_{k+2}-2F_{k}>F_{k+2}-F_{k}=F_{k+1}.\]  
Therefore, \(u+v^{\prime}\) can only take one value as a Fibonacci number: \(F_{k+2}\). This value cannot be the label on this edge because it corresponds to the label of the uu' edge (and the vv' edge too). Hence, \(uv^{\prime}\) cannot be an edge. By the symmetry of \(u\) and \(v\), we obtain that \(u^{\prime}v\) is not an edge either. It will be shown that these cycles, along with the loop edges, are the essential cycles in \(F\). Therefore, it is not difficult to sparsify the \(F\) graph to obtain a tree. This is in spite of the fact that some of the 4-cycles share a common edge; hence, they form longer cycles in \(\mathcal{G}\). **Definition 4**. : _Let \(\mathcal{F}_{0}\) be the graph obtained from \(\mathcal{F}\) by removing the edges connecting \(0\) to Fibonacci numbers with odd indices, the loop edges, and the \(u^{\prime}v^{\prime}\) edges of the 4-cycles \(C_{k}(a)\)._  
**Theorem 6**. : \(\mathcal{F}_{0}\) _is a tree._  
The theorem points out a spanning tree of \(\mathcal{F}\): \(\mathcal{F}_{0}\). Proof. : Let \(\mathcal{F}_{0}(n)\) be the spanning subgraph of \(F_{0}\) formed by the vertices \(0,1,2,\ldots,n\) and the edges between them. It is sufficient to show that for any \(n\), this graph is cycle-free and connected. For small values of \(n\), it is easy to verify the statement. See \(\mathcal{F}_{0}(25)\) on Figure 2.  
By induction, we prove that \(\mathcal{F}_{0}(F_{k})\) is a tree. Assume that we know this for \(\mathcal{F}_{0}(F_{\ell})\). We add the vertices \(F_{\ell}+1,F_{\ell}+2,\ldots,F_{\ell+1}-1,F_{\ell+1}\) to it and check that our graph remains a tree. We do this by proving that by adding any of these numbers it will be connected to exactly one earlier (smaller) node. Figure 2: The tree \(\mathcal{F}_{0}(25)\). In the case of \(F_{\ell+1}\), this is true. In \(\mathcal{F}\), there are two earlier neighbors of it: \(0\), and \(F_{\ell}\). If \(\ell+1\) is even, then \(0\) is connected to \(F_{\ell+1}\), but \(F_{\ell}F_{\ell+1}\) is the deleted edge of \(C_{\ell-2}(0)\) in \(\mathcal{F}_{0}\). If \(\ell+1\) is odd, then \(0F_{\ell+1}\) is a deleted edge, but \(F_{\ell}F_{\ell+1}\) is a remaining edge of \(C_{\ell}(0)\) in \(\mathcal{F}_{0}\). The same logic works in the case of \(F_{\ell}+i\), where \(0<i<F_{\ell-1}\). In \(\mathcal{F}\), there are two earlier neighbors of it: \(F_{\ell+1}-(F_{\ell}+i)=F_{\ell-1}-i\), and \(F_{\ell+2}-(F_{\ell}+i)=F_{\ell+1}-i\). The two connecting edges are in two 4-cycles. In one of them, the edge is deleted; in the other, it is not deleted. \(F_{\ell}+i\) has exactly one earlier neighbor in \(\mathcal{F}_{0}\). As previously, we can label the edges. The label of an edge will be the sum of the numbers corresponding to its endpoints. The labels are Fibonacci numbers. Lemma 5: _Consider \(\mathcal{G}_{0}\) as a graph with labeled edges. In this case, the edge labeling possesses the following two properties:_  
1. _The edges incident to_ \(0\) _have labels that are even-indexed Fibonacci numbers._
2. _The labels of two adjacent (sharing a common endpoint) edges cannot correspond to Fibonacci numbers with consecutive indices._  
Proof: The labeling can also be introduced for the edges of graph \(\mathcal{F}\). It is worth noting that both statements are false in \(\mathcal{F}\). In \(\mathcal{F}_{0}\), both statements become true due to the definition of \(\mathcal{F}_{0}\), which is a result of sparsifying \(\mathcal{F}\). In \(\mathcal{F}\), all Fibonacci numbers appear on edges incident to \(0\). In the definition of \(\mathcal{F}_{0}\), we precisely excluded those edges whose labels correspond to odd-indexed Fibonacci numbers. This yields statement (a). Let us consider two adjacent edges in \(\mathcal{F}\) with label Fibonacci numbers that correspond to consecutive indices.