How many ways to make a connected graph using 4, 5, 6 edges?

Question

How can/how many ways can you make a connected graph that has 5 vertices using 4, 5, 6 edges?

I'm not sure how it would look like for 4 edges. Can you draw a diagram?

Answer 1

For $4$ edges: $${\rm X}\qquad {\rm W}\qquad \vdash$$

Answer 2

The diagram would be like

For an edge to be placed remember that you must choose $2$ vertices and be careful about bijection, by that i mean that if you do not label the vertices this two graphs (see below) are identical.

Edit: As commented, because they are just a few, you can iterate all the ways (without order i.e. $2+2+2+1+1=2+1+2+2+1=\ldots =1+1+2+2+2$) you can put a number in the degrees of your graph by recalling $\sum _{v\in V}\deg(v)=2|E|$. In the diagram above is the graph with degrees $2,2,2,1,1$.
Hope this helps.

Answer 3

If your graph has $4$ edges, it must be a tree (a tree is a graph with no cycles). To see this, notice that if it had a $5$-cycle it would have $5$ edges, if it had a $4$-cycle it would have no edge connecting to the vertex outside the cycle, and if it had a $3$-cycle it would be disconnected, either because the $4$th edge connects the two other vertices and we have two connected components, or the $4$th edge connects one of the two other vertices to our $3$-cycle and the fifth point would be disconnected. Conversely, any connected tree with $5$ vertices has four edges (any connected tree with $n$ vertices has $n-1$ edges ; you can prove this easily by induction on $n$).

Now to build all possible trees, start with one vertex $v_0$, and decide how many vertices will be "at distance $1$" of $v_0$ (i.e. those whose shortest path to $v_0$ consists of one edge), then those "at distance $2$", and so on. In other words, look at all partitions of $5$ where two partitions differing by commutativity of addition are considered distinct ; then put edges between all pairs of vertices $(v,v')$ for which the difference between the distance $d(v,v_0)$ and $d(v',v_0)$ is $\pm 1$.

After doing this list, you'll find only three pairwise non-isomorphic graphs, namely the line ($\cdot - \cdot - \cdot - \cdot - \cdot$), this ($\cdot - \cdot - \cdot < :$) and the star graph on $5$ vertices (which looks like $+$).

If it has $5$ vertices and $5$ edges, you already know what to do if the graph has no cycles ; repeat the previous procedure. Then you can distinguish cases where it has a $3$-cycle, $4$-cycle and $5$-cycle ; $5$-cycle and $4$-cycle are easy (there is only one graph in each case), and for a $3$-cycle there are only two ways of making it connected ; either you link the two remaining vertices by an edge or not.

For $5$ vertices and $6$ edges, you're starting to have too many edges, so it's easier to count "backwards" ; we'll look for the graphs which are not connected. You clearly must have at most two connected components (check this), and if your two connected components have $(3,2)$ vertices, then the graph has $3$ or $4$ edges ; so our components must have $(4,1)$ vertices. But then there is only one case ; the complete graph $K_4$ together with an extra point. So all graphs with $5$ vertices and $6$ edges (except $K_4$ with an extra point) are connected.

Hope that helps,