Return to Answer

The above can be readily extended to accommodate hypergraphs (allow more than one vertex per 'edge'), digraphs (use primes to represent ordered pairs instead of unordered pairs), and other generalizations; one only needs to choose a suitable representation, and store it in an integer in some way which can be extracted. These are standard tricks in computability theory; we are just adapting Godel numbering for a special purpose in this case.

The above can be readily extended to accommodate hypergraphs (allow more than two vertices per 'edge') and other generalizations; one only needs to choose a suitable representation, and store it in an integer in some way which can be extracted. These are standard tricks in computability theory; we are just adapting Godel numbering for a special purpose in this case.

We may induce adjacency among the vertices by giving them appropriate common prime factors. A simple way to do this is to associate a prime to each edge, and give any two vertices belonging to a common edge the corresponding prime factor. (Vertices which do not share an edge in common will have no common prime factors, and thus be coprime.) We order the possible edges by considering the lexicographic ordering on all ordered pairs $(v_j, v_k)$ such that $v_j < v_k$: thus the possible edge $v_j v_k$ (for $j < k$) will be edge number $\varepsilon(j,k) = \binom{k-1}{2} + j$ in the enumeration. More generally, we may define $$ \varepsilon(j,k) = \binom{\max \{j,k\} - 1}{2} + \min \{j,k\} .$$ We may represent the adjacency of two vertices $v_j, v_k$ by giving their corresponding integers $n_j, n_k$ a common prime factor, namely the prime $p_{\varepsilon(j,k)}$. The exponents of the primes $p_{n+1}$ through $p_{n+\binom{n}{2}}$ in the integers $n_j$ as forming an incidence matrix of edges to vertices.

We may induce adjacency among the vertices by giving them appropriate common prime factors. A simple way to do this is to associate a prime to each edge, and give any two vertices belonging to a common edge the corresponding prime factor. (Vertices which do not share an edge in common will have no common prime factors, and thus be coprime.) We order the possible edges by considering the lexicographic ordering on all ordered pairs $(v_j, v_k)$ such that $v_j < v_k$: thus the possible edge $v_j v_k$ (for $j < k$) will be edge number $\varepsilon(j,k) = \binom{k-1}{2} + j$ in the enumeration. More generally, we may define $$ \varepsilon(j,k) = \binom{\max \{j,k\} - 1}{2} + \min \{j,k\} .$$ We may represent the adjacency of two vertices $v_j, v_k$ by giving their corresponding integers $n_j, n_k$ a common prime factor, namely the prime $p_{n+\varepsilon(j,k)}$. The exponents of the primes $p_{n+1}$ through $p_{n+\binom{n}{2}}$ in the integers $n_j$ then form the incidence matrix of edges to vertices in $G$.