The question is: How many different undirected graphs are there with n nodes and

Question

The question is:

How many different undirected graphs are there with n nodes and no parallel edges but may include self-loops?

I've been wracking my brain over this for hours now. Basically, I know that for 1 vertex, there are 2 graphs. For 2 vertices, there are 8 graphs. For 3 vertices, there are 64 graphs. However, I can't connect these numbers without my answer for 1 vertices not working. For example, the equation number of graphs equals $2^{3n-3}$ works for 2 and 3 vertices, but not for 1. Any opinions on the connecting equation?

Explanation / Answer

Undirected graphs with self-loops on $n$ vertices have $inom{n}{2} + n = inom{n+1}{2}$ potential edges. Therefore the are $2^{inom{n+1}{2}}$ different graphs. For $n = 1,2,3,ldots$, this is $$ 2^1, 2^3, 2^6, 2^{10}, 2^{15}, 2^{21}, 2^{28}, 2^{36}, 2^{45}, 2^{55}, ldots $$

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.