The Full Question

Find all(loop-free) non-isomorphic, undirected graphs with four vertices. How many of these graphs are connected?

My Work(Ideas)

I'm a little infuriated at this question because it is supposed to be easy, but I can't seem to crack it. I suppose we must have 4 vertices, so I could go through all graphs with zero edges, 1 edges, 2 edges, 3 edges, etc. This seems like it might go on for a long time(i.e. the rest of my natural life). I suppose we may reach a point where all I can make is loops if I add more edges?(I have no idea where this would be) Could anyone maybe offer me a helping hand with this question? I'm fairly confused

  • $\begingroup$ I assume no multiedges are allowed. $\endgroup$ – Jorge Fernández Hidalgo Mar 24 '15 at 5:47
  • $\begingroup$ I'm not sure. I quoted the text verbatim under the header "The Full Question". Removing multiedges would seem to remove my concern of doing this problem for the rest of my natural life though? @TheEmperorofIceCream $\endgroup$ – Dunka Mar 24 '15 at 5:49
  • $\begingroup$ yes, it would, it shouldn't take too long to do it like that. $\endgroup$ – Jorge Fernández Hidalgo Mar 24 '15 at 5:49
  • 1
    $\begingroup$ I went through all graphs from 0 edges up to 6 edges (the maximum) and it took me about 2 minutes. Probably less time than it took you to type your question. (Well, less time than it would have taken me to type it, but you're probably a faster typist than I am.) I found 1 graph with 0 edges, 1 graph with 1 edge, 2 graphs with 2 edges, 3 graphs with 3 edges. After then it got easier: the 4-edge graphs are just the complements (missing-edge graphs) of the 2-edge graphs, etc.; so 2 4-edge graphs, 2 5-edge graph, 1 6-edge graph, for a total of 1+1+2+3+2+1+1 = 11 graphs, 6 of which are connected. $\endgroup$ – bof Mar 24 '15 at 6:56

There aren’t all that many, and yes, you can go through the possibilities from $0$ edges through $\binom42=6$, the maximum possible. I’ll get you started.

$0$ edges: $1$ graph:

       *   *   *   *

$1$ edge: $1$ graph:

       *---*   *   *

$2$ edges: $2$ graphs, because the edges can be disjoint or share a vertex:

       *---*   *---*                     *---*---*   *

$3$ edges: The edges can’t all be disjoint: that would require $6$ vertices. Thus, we must have


as part of any such graph. There are $3$ possibilities:

       *---*---*---*                  *---*---*                *---*   *  
                                          |                     \ /  
                                          *                      *

Can you see why no two of these are isomorphic, and why they are the only possibilities?

I’ll leave the rest to you for now. There are very few non-isomorphic possibilities for $6$ edges and for $5$ edges, so perhaps you should start with those cases. The only case that should take a bit of work is the case of $4$ edges.

  • $\begingroup$ It's helpful too that there's a duality between such graphs with $k$ edges and such graphs with $6 - k$ edges, simply by taking a graph, drawing edges between vertices that didn't share them and then removing the edges of the given graph. So, one only needs to classify graphs with $\leq 3$ edges, and the rest is just procedural. $\endgroup$ – Travis Willse Mar 24 '15 at 6:08
  • $\begingroup$ @Travis: True, though I think that it’s probably a good exercise for a rank beginner to do it in the most straightforward way first (unless he comes up with that idea on his own, of course). $\endgroup$ – Brian M. Scott Mar 24 '15 at 6:11

I think separating into the number of edges is a good idea. The number of edges goes from $0$ to $6$ so you won't take that long. The number of such graphs is bounded by $2^6=64$ since this is the number of graphs on vertex set $\{1,2,3,4\}$ up to labelling.

If you get confused midway you can also separate depending on the degree sequence of the graph.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.