Let $G$ be a $4$-regular graph on $7$ vertices, and let $\overline{G}$ be the complement of $G$. $\overline{G}$ is regular; what is its degree (what you called order in your question)? What do you know about regular graphs of that degree? They’re very easy to count, and since $G_1$ is isomorphic to $G_2$ iff $\overline{G_1}$ is isomorphic to $\overline{G_2}$, counting the complements is as good as counting the graphs themselves.
(Note that the answer depends greatly on whether you’re counting labelled or unlabelled graphs. Also, I’m assuming that you’re looking only at simple graphs, i.e., without loops or multiple edges.)
Added:
To see that counting the complements is good enough, let $\mathscr{G}_n$ be the set of all simple graphs on $n$ vertices, and let $\varphi:\mathscr{G}_n\to\mathscr{G}_n:G\mapsto\overline{G}$ be the map that takes each graph in $\mathscr{G}_n$ to its complement. Then show that $\varphi$ is a bijection, and that $G\in\mathscr{G}_n$ is $k$-regular iff $\varphi(G)=\overline{G}$ is $(n-1-k)$-regular.
The graph isomorphism problem is "a curiousity" according to the Wikipedia article, because it is one of very few problems which are NP but not known either to be in P or to be NP-complete. There are algorithmic approaches, but these are not closely related to group theory except in the general sense of using symmetries, and they are often very tractable by known methods. Brendon McKay's NAUTY was the first to produce all the 11 vertex ($n=11$) graphs up to isomorphism, and can check most pairs of graphs up to 100 vertices for isomorphism rather readily.
OEIS A000088 gives a tablulation of known results for $n=0,1,2,\ldots,19$ and some useful references.
Pictures of the eleven possible (up to isomorphism) simple graphs on four vertices are easily sketched as you'll see below.
To prove these are exhaustive, one might focus on some graph properties that are preserved by isomorphism (graph invariants). An easy one is the number of connected components. As shown in the diagrams, we need to account for one graph with four components, one with three components, three with two components, and six that are connected (one component).
Other easy graph invariants are the number of edges, the collected degrees of vertices (degree sequences), and the number of 3- and 4-cycles (possibly zero).
Since the diagrams shown at the link above are arranged by number of edges, which ranges from $0$ (no edges) to $6$ (complete graph $K_4$), it's perhaps the way to begin, first to assure us that all eleven graphs really are non-isomorphic, and second to assure us there is no overlooked possibility.
The extremes (no edges, one edge, six edges) all give unique graphs, and a moments reflection will tell you that five edges also gives a unique graph (because you are picking any one of the edges of the complete graph to remove, and all those choices are equivalent).
There are two cases with two edges, which you should convince yourself differ by whether the edges connect or not, and that these exhaust all possibilities for two edges on four vertices.
The two cases with four edges are similarly distinguished by whether we remove two edges (from the complete graph) that connect or not. Note that removing two edges that do not connect leaves a four-cycle (each vertex has degree two), where removing two edges that do connect leaves one "terminal" vertex of degree one, so that these are clearly non-isomorphic (and exhaust all possibilities).
The three cases with three edges are the most interesting, because as a class these are closed under complementation. One (threeB) is the smallest nontrivial self-dual simple graph, a graph isomorphic to its complement. The other two (threeA and threeC) are complementary to each other and clearly not self-dual (threeC is connected and its complement is not; threeA contains a cycle and its complement does not).
To see that these exhaust the possibilities for three edges, note that any tree (a cycle-free connected graph) on four vertices will have precisely three edges. If a graph on four vertices with three edges has a cycle, that must be a triangle (3-cycle) since we don't have enough edges for anything bigger. Otherwise we have a tree, and the tree must either consist of one vertex of degree three connecting to the other three vertices, or else a path of three edges that connects all the vertices.
Best Answer
That's right, the first is a connected graph, the second is a graph that isn't connected.
What is true is that all connected $2$-regular graphs with $n$ vertices are isomorphic, being $n$-cycle graphs.