Nodes and edges with combinatorics!

Question

Given N number of nodes how many different configurations are possible (with nodes not being labelled i.e. all nodes are identical) with the condition that there is no isolated node. That is not the complete question. The big question is what if we restrict the node to have no more than 4 edges connected to it and that they don't form rings. The solution to first is trivial if the nodes are labelled:
The first node has $2^{N-1}-1$ the second $2^{N-2}-1$ the third $2^{N-3}-1$ and so on.. Therefore the total number of possibilities are $$\frac{2^N-1}{1}-N$$ All we need to do is divide this number with number of possible arrangements of these lables among themselves note that it's not $N!$ due to some symmetries.
Something inside me says there could be a recurrence relation lurking.

Answer 1

You are asking several questions of various difficulties, which I will rephrase in common graph theory vocabulary:

1. How many labeled graphs have no isolated nodes?
2. How many labeled graphs are trees with every vertex having degree at most $4$?
3. How many unlabeled graphs have no isolated nodes?
4. How many unlabeled trees are trees with every vertex having degree at most $4$?

Your solution to $(1.)$ does not quite work. For each node, you are choosing the edges out of each node, which would mean you have to multiply the numbers $(2^{N-i}-1)$, not add them. Furthermore, there are more choices than you have accounted for. You used $2^{N-i}-1$ so every node is connected to some node after it, but it is OK for a node to have no connections after it as long as it had some connections before. The choice is therefore sometimes $2^{N-i}-1$ and sometimes $2^{N-i}$.

The only way to resolve these complicated dependencies is to use the principle of inclusion exclusion. Namely, count the number of graphs, then for each vertex subtract the graphs where that vertex is isolated, the for each pair of vertices add back in graphs where both of those vertices are isolated, etc. The result is $$ \sum_{k=0}^n (-1)^k\binom{n}k 2^{\binom{n-k}{2}} $$

For $(2.)$, things are even trickier. I think you have to use Prüfer codes, which are a bijection between labeled trees on $\{1,2,\dots,n\}$ and lists of length $n-2$ with entries in $\{1,2,\dots,n\}$, such that the degree of each vertex $i$ is one plus the number of times $i$ appears in the list. Therefore, the number of such labeled trees is $$ \sum_{\substack{\sum_{i}d_i=n-2\\\max d_i\le 3}} \binom{n-2}{d_1,d_2,\dots,d_n} $$ This is a large summation of multinomial coefficients which I believe cannot be simplified.

Unfortunately, I have little hope of getting closed form expressions for $(3.)$ or $(4.)$. There is no known expression for the number of unlabeled graphs, full stop. As you said, the number of symmetries makes things complicated. You may be able to do something using Polya's enumeration method to handle the symmetries, but this will result in a summation over $n!$ terms which will quickly get computationally infeasible.