NeuroEvolution: NEAT algorithm innovation numbers
Here is what I gathered from skimming the paper for just the figure.

Your first figure, which is the figure 3 in the paper, already has the answer in its caption:


  Figure 3: The two types of structural mutation in NEAT. Both types,
  adding a connection and adding a node, are illustrated with the
  connection genes of a network shown above their phenotypes. The top
  number in each genome is the innovation number of that gene. The
  innovation numbers are historical markers that identify the original
  historical ancestor of each gene. New genes are assigned new
  increasingly higher numbers. In adding a connection, a single new
  connection gene is added to the end of the genome and given the next
  available innovation number. In adding a new node, the connection gene
  being split is disabled, and two new connection genes are added to the
  end the genome. The new node is between the two new connections. A new
  node gene (not depicted) representing this new node is added to the
  genome as well.


In figure 3, it could be deduced that the add connection mutation (top half) occur preceding  the add node mutation (buttom half).


When the add connection mutation occurred, the lowest free innovation number was 7. And so the gene created at that moment was assigned the marker of 7.
Later, when the add node mutation occurred, 2 new genes were created. And so they were assign the lowest free innovation number at the time which is 8 and 9.


The innovation number is not the indices of each gene inside the array representing a genome.

The innovation number is just a number permanently branded to each gene, telling us when the gene first occur. As if the year number when human first evolved a gene for hairless body were written down on the gene itself.

The uses of innovation is then explained around your latter figure, which is figure 4:


  The historical markings give NEAT a powerful new capability. The
  system now knows exactly which genes match up with which (Figure 4).
  When crossing over, the genes in both genomes with the same innovation
  numbers are lined up. [...]
  This way, historical markings allow NEAT to perform crossover using linear genomes with out the need for expensive topological analysis.


From this I assumed that innovation number are always ordered increasingly within a genome, but gaps in innovation numbers are allowed to occur within genome.
The order is probably ensured simply by the fact that all operations done on genome was designed to not violate this within-genome ordering.

This makes sense because each gene can be thought of as an instruction to construct a graph.
By keeping the instruction ordered by when it was introduced, it makes sure that reading instruction on genome from left to right makes sense chronologically.