This will be true if you allow loops and multiple edges - just equate the lengths of the cycles in any such graph with order n with the parts of a partition of n :)

Peter Breuer My understanding is that Maged is speaking of graphs in which each vertex has degree two, so disjoint unions of cycles. If we allow cycles of length one or two, then his observation will be correct.

Let P(n) be the number of partitions of the positive integer n. P(1)=1, P(2)=2, P(3)=3, P(4)=5, P(5)=7, P(6)=11, and P(7)=15. There is one undirected graph of one vertex of degree 2, two graphs of two vertices each of degree 2, three graphs on 3 vertices each of degree 2, and ..., there are 15 graphs of order 7 each of degree 2(as P(7)=15).

We mean by an undirected graph, which allows loops and multiple edges, often called psuedograph.

Let's consider the case n=4. There are 5 graphs of degree sequence 2,2,2,2. That consists of four vertices each of degree 2, which are: 1- the graph consists of four disjoint loops, 2- the graph consists of 2 disjoint loops and 2 multiple edges, 3- the graph consists of the disjoint union of two multiple edges, 4- the graph consists of the disjoint union of a loop and a cycle of length 3, and 5- the cycle of length 4.

Peter Breuer Remember that loops by convention typically count as two towards the degree of the vertex that they are attached to :) So the correspondence is natural for pseudographs.