# Binary Numeration System with Alternating Signed Digits and Its Graph Theoretical Relationship
## 3 Connection to Graph Theory  
Let \(G=(V,E,I)\) be a triple. The elements of \(V\) are called vertices; \(V\) is the vertex set of \(G\). The elements of \(E\) are called edges; \(E\) is the edge set \(G\). \(I\) is an incidence relation between \(V\) and \(E\) (\(I\subset V\times E\)). If \(v\in V\) and \(e\in E\) are incident, then we say that the vertex \(v\) is an endpoint of the edge \(e\). We call \(G\) a graph if every edge has two endpoints. These two endpoints may coincide, in which case \(e\) is called a loop. If an edge \(e\) has two endpoints \(u\) and \(v\), then we say that \(u\) and \(v\) are connected by \(e\) or \(u\) and \(v\) are adjacent. If two edges have the same two endpoints, then we say that they are parallel edges. If there are no parallel edges in a graph, we only need to describe when two vertices are connected to define the graph. Moreover, if a graph contains no loops, then we call it a simple graph. If \(V\) and \(E\) are finite sets, then \(G\) is a (finite) graph. If \(V\  
Proof. : We can think about \(\mathcal{G}_{0}(n)\) as a result of the following sequence of graph extensions:  
\[\mathcal{G}_{0}(1)\to\mathcal{G}_{0}(2)\to\mathcal{G}_{0}(3)\to\ldots\to\mathcal{ G}_{0}(n-1)\to\mathcal{G}_{0}(n).\]  
The initial graph \(\mathcal{G}_{0}(1)\) is a graph with one node (1) and no edge, i.e., \(\mathcal{G}_{0}(1)\) is the smallest tree. Each expansion step is a \"branching\" (we extend our actual graph with a new vertex and a new edge that connects the new node to an old one). This operation preserves connectivity and cycle-freeness. That is, the operation forms a tree from a tree. **Corollary 1**. : \(\mathcal{G}_{0}\) _is a tree._  
Thus, there is exactly one path from any vertex, let us call it \(n\), to the vertex \(0\). We assume that \(n\
eq 0\). For each edge, label it with the sum of its two endpoints. Thus, we obtain an edge-labeled graph (the labels are powers of two). As the path from \(n\) to \(0\) is traversed, the labels of its edges strictly decrease. The walks with strictly decreasing labels from \(n\) to \(0\) are exactly the paths from \(n\) to \(0\) (that happen to be unique). This is not true in \(\mathcal{G}\). There is a second walk from \(n\) to \(0\) with strictly decreasing edge labels, a walk where the penultimate step is a loop. The above graph theoretic remark and the alternating binary number system are closely related. The next theorem formalizes this. **Theorem 5**. : _Let \(n\) be a positive integer. Let \(\mathcal{W}_{n}\) be the set of \(n\to 0\) walks in \(\mathcal{G}\) with strictly decreasing edge labels. Let \(\mathcal{R}_{n}\) be the set of alternating binary representations of \(n\)._  
_Then, there is a bijection between \(\mathcal{W}_{n}\) and \(\mathcal{R}_{n}\)._  
Remember that \(\mathcal{G}\) is almost the same as the \(\mathcal{G}_{0}\) graph (a tree), except there are additional loops at the neighbors of \(0\). Hence, \(\mathcal{W}_{n}\) consists of two walks: the unique \(n\to 0\) path \(P\) in \(\mathcal{G}_{0}\), and a walk that is the same as \(P\), except that just before reaching \(0\) we go along a loop. The bijection, presented below, proves that \(\mathcal{R}_{n}\) also has two elements, which is the statement of Theorem 2. We can consider Corollary 1 as the graph theoretical analog of Theorem 2. Proof. : Let \(n=2^{\alpha}-2^{\beta}+2^{\gamma}-2^{\delta}\pm\ldots\) be an arbitrary alternating binary representation of \(n\) (an element of \(\mathcal{R}_{n}\)). We introduce the following numbers: \(n_{0}=n=2^{\alpha}-2^{\beta}+2^{\gamma}-2^{\delta}\pm\ldots\), \(n_{1}=2^{\beta}-2^{\gamma}+2^{\delta}\mp\ldots\), \(n_{2}=2^{\gamma}-2^{\delta}\pm\ldots\), \(n_{3}=2^{\delta}\mp\ldots\), \(\ldots\), \(0\). These numbers: \(n_{0}=n\), \(n_{1}\), \(n_{2}\), \(\ldots\), \(n_{\ell-1}\), \(n_{\ell}=0\) are vertices in \(\mathcal{G}\), and they form a sequence of vertices of walk from \(n\) to \(0\). The labels of the edges are \(2^{\alpha}>2^{\beta}>2^{\gamma}\ldots\). Figure 1: The tree \(\mathcal{G}_{0}(26)\).