I apologize in advance for my abuse of set notation as I am mapping one mathematical object that is not quite a set i.e. graphs to another mathematical object that is not quite a set i.e. sequences. Feel free to comment or correct notation etc.

**Definitions:**

**(1) The triangular-harmonic numbers** $\Theta$ are a monotonic sequence of rational numbers greater than or equal to one defined recursively as follows:

$$\Theta := \bigcup_{\forall k}\{\theta_k \in\mathbb Q\mid \theta_k \geq 1\}\\
\theta_0 = 1\\
\theta_k = \theta_{k-1}+\frac{1}{\lfloor \theta_{k-1}\rfloor} $$
The first few terms of $\Theta$ are:
$$\left\{1,2,2+\frac{1}{2},3,3+\frac{1}{3},3+\frac{2}{3},...\theta_k\right\}$$

I am grateful to Carlo Beenakker for helping me find the closed form of $\Theta$ which is $\theta_k=\frac{T_k^{-1}}{2}+\frac{k}{T_k^{-1}}+\frac{1}{2}$ for $k\geq 1$ where $T_k^{-1}=\left\lfloor\sqrt{2n}+\frac{1}{2}\right\rfloor$ is the inverse triangular number function.
https://oeis.org/A002024

**(2) The index function of** $\theta_k$ is found by solving the closed form for $k$:
$$k(\theta_k)=\frac{2\lfloor \theta_k \rfloor \theta_k- \lfloor \theta_k \rfloor^2- \lfloor \theta_k \rfloor}{2}$$

**(3) The edge-value function** $\mathcal E$ is a function that maps the edges of a natural number-labelled graph to the rational numbers as follows:

\begin{equation}
\text{if }\ G=(V,E) \text{ with }\ V=\{1,2,3 ...n\}\Longrightarrow\exists \mathcal E:E\mapsto \mathbb Q\\
\mathcal E(e_{ij})=\frac{j^2+i}{j}=j+\frac{i}{j}\\ \text{ where }\ i<j \text{ and }\ i,j \in V
\end{equation}

**Theorem: The rationally-ordered graph theorem.**

Claim:
If the vertices of a simple graph are uniquely labeled with integers, then the whole graph can be uniquely mapped to a monotonic sequence of
rational numbers that is a subset of $\Theta$ the triangular-harmonic numbers.

If $V(G)=\{1,2,3 ..., n\} \Rightarrow \exists \text{ sequence } S_k$ of monotonically increasing rational numbers where $S_k<S_{k+1}$ for all $k$ and $ \{S_k\}_{\forall k} \subset \Theta$.

Proof:

Consider building a sequence of complete graphs over n vertices, one vertex at a time, starting with the one-vertex complete graph $K_1$ labeled with the integer 1.
$$\text{Let }\ K_1 = (V,E) = (\{1\},\{\})\\$$
Adding a second vertex and applying the previously defined edge-ordering function $\mathcal E(e_{ij})\mid e_{ij}\in E(K_n)$ over all edges in $K_2$ gives us:

$$K_2 \longmapsto V(K_2) \bigcup_{\forall e_{ij} \in E(K_2)} \mathcal E(e_{ij})=\left\{1,2,2+\frac{1}{2}\right\}$$

$$K_3 \longmapsto V(K_3) \bigcup_{\forall e_{ij} \in E(K_3)} \mathcal E(e_{ij})=\left\{1,2,2+\frac{1}{2},3,3+\frac{1}{3},3+\frac{2}{3}\right\}$$
$$\cdot$$
$$\cdot$$
$$\cdot$$
$$K_n \longmapsto V(K_n) \bigcup_{\forall e_{ij} \in E(K_n)} \mathcal E(e_{ij})=\left\{1,2,2+\frac{1}{2},3,3+\frac{1}{3},3+\frac{2}{3}, … ,n,n+\frac{1}{n}, ..., n+\frac{(n-1)}{n}\right\}$$

Simple inspection shows that $K_n \longmapsto S= \{\theta_k\}_{k=0}^{T_n-1}$ where $T_n$ denotes the $n^{th}$ triangular number i.e. $T_n=\frac{n^2+n}{2}$.

Now consider that all simple graphs of order n are spanning subgraphs of the complete graph of order n and it becomes clear that the rational sequence of any finite simple graph is a finite subsequence of the trianguar-harmonic numbers:

$$\text{If } G_n \in \{\text{simple graphs}\}\text{ and }G_n \subset K_n \Longrightarrow G_n \mapsto S \mid S \subset \Theta\\ \blacksquare$$

**Corollary 1: Index of simple graphs** There exists an index on all simple graphs of order $n$ such that the computational complexity of each of the indices is on the order of $ O(n^2)$ bits.

Proof:
Given a simple graph $G=(V,E)$ of order $n$, one uses the rationally ordered graph theorem to derive a "graph sequence" $S$ of rational numbers such that the integers denote vertices $V = \{v_1,v_2,v_3,...,v_n \mid v_n \in \mathbb N \}$ while improper fractions denote the edges between them $E=\left\{\frac{v_j^2+v_i}{v_j}\mid v_i < v_j \text{ for }\forall (v_i,v_j) \in E\right\}\text{ }\therefore S(G\mapsto\Theta)=V \cup E$.

Since from the ROG theorem we know that $S \subset \Theta$ we can simply find the index number of graph $G$ by calculating the sum:
$$I(G)=\sum_{\forall i \in S} 2^{k(i)}$$

Therefore for a graph $G_n$ of order $n$ between the limits of an empty graph and a complete graph we have:
$$\sum_{i=1}^{n}2^{T_n-1} \leq I(G_n) \leq 2^{T_n}-1$$

Since $\lim_{n\to\infty}T_n=\lim_{n\to\infty}\frac{n^2+n}{2}=\lim_{n\to\infty}n^2=\infty\Longrightarrow O(n^2)$
$$\blacksquare$$

8more comments