# Find All NonIsomorphic Undirected Graphs with Four Vertices

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

• I assume no multiedges are allowed. – Jorge Fernández Hidalgo Mar 24 '15 at 5:47
• 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 – Dunka Mar 24 '15 at 5:49
• yes, it would, it shouldn't take too long to do it like that. – Jorge Fernández Hidalgo Mar 24 '15 at 5:49
• 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. – 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.

• 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. – Travis Willse Mar 24 '15 at 6:08
• @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). – 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.