Question

Counting the number of connected undirected simple graphs with \(n\) distinct vertices and \(k\) edges.

Answer 1

\[
n-1<k<{n\choose 2}
\]

Answer 2

\[
\begin{array}{c|c|c}
n&k_{\min}&k_{\max} \\
\hline
2&1&1\\
3&2&3\\
4&3&16\\
5&4&10\\
6&5&15\\
7&6&21\\
8&7&28
\end{array}
\]

Answer 3

\[
n-1\leq k\leq {n\choose 2}
\]

Answer 4

\[
{n\choose 2} = \frac{n(n-1)}{2}
\]

Answer 5

this a graph with 2 vertices and 0 edges
so here we have n=2 and k=0
but your inequality says this
\[n-1\leq k\leq {n\choose 2}\]
\[1 \leq 0 \leq 0\]
but 0 isn't greater than 1

Answer 6

Are we only looking at what its called?
connected graphs or is it called complete graphs?
can't remember

Answer 7

Connected graphs

Answer 8

I think connected has something to do with directions
and complete graphs is actually what you are looking for https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=13&cad=rja&uact=8&ved=0CGcQFjAM&url=https%3A%2F%2Fwww.math.ku.edu%2F~jmartin%2Fcourses%2Fmath105-F11%2FLectures%2Fchapter6-part2.pdf&ei=fSE0VYyqBseRoQSskoHIAw&usg=AFQjCNFip_uWUDFQT4wcX5dk497V09RYvQ&bvm=bv.91071109,d.cGU

Answer 9

so here's the adjacency matrix for this graph so reading down the second column this means 1 connects to 2, 2 doesn't connect to itself, and 2 doesn't connect to 3. \[\left[ \begin{array}c 0 & 1 & 1\\1 & 0 & 0\\1 & 0 & 0\\\end{array} \right]\] Squaring this matrix gives us \[\left[ \begin{array}c 2 & 0 & 0\\0 & 1 & 0\\0 & 0 & 1\\\end{array} \right]\] which seems weird, but makes sense especially in the context of directed graphs. Just imagine the edges are all directed in both directions.