identifying non isomorphic graphs with no comparison graph

Question

hi one of my homework problems is "Draw all nonisomorphic simple graphs with four vertices" my issue with this is that I thought isomorphism was used as a comparison, so how would you start to draw a graph that is non isomorphic?

Answer 1

It means, draw a representative of all possible isomorphism classes. For instance if it was two vertices instead of four, you only have the graphs

$$V=\{0,1\}, E=\emptyset$$ and $$V=\{0,1\}, E=\{(0,1)\}$$

as any other simple graph on two vertices will be isomorphic to one of these two.

---

To perhaps demistify the wording of the problem a little. The question is asking you the following.

Draw 11 simple graphs with four vertices so that no two graphs are isomorphic to each other.

Above, I have shown all 2 simple graphs with two vertices such that no two graphs are isomorphic to each other, now you should try to do it with four vertices.

Answer 2

You don’t draw ‘a graph that is non-isomorphic’; that is a meaningless expression for the reason that you gave, namely, that isomorphism is a property of pairs of graphs. You draw a simple graph with four vertices. Then you find another simple graph with four vertices that is not isomorphic to the first graph. Then you try to find a third simple graph with four vertices that is not isomorphic to either of the first two. And you keep going until you reach the point at which every possible simple graph with four vertices is isomorphic to one of the graphs that you’ve already drawn.

Answer 3

The question asks to draw all possible simple graphs on $4$ vertices such that no two of the graphs drawn are isomorphic.

The complete graph $K_4$ has $6$ edges, and it is possible to either choose or not choose each edge. The choices made for each of these edges gives a particular (labeled) graph on $4$ vertices. The path graph consisting of edge set $\{12, 23, 34\}$ and the path graph consisting of edge set $\{23, 34, 41\}$ are different as labeled graphs but are isomorphic (ie are in the same isomorphism class). More generally, if $V=\{1,\ldots,n\}$ and $V^{\{2\}}$ is the set of all $2$-subsets of $V$, then $|V^{\{2\}}| = {n \choose 2}$, and the set of $2^{n \choose 2}$ subsets of $V^{\{2\}}$ corresponds to the set of all $2^{n \choose 2}$ labeled graphs on $n$ vertices. This set can be partitioned into isomorphism classes, ie the partition is such that two labeled graphs are in the same part if and only if they are isomorphic.

The set of $2^{4 \choose 2} = 2^6 = 64$ different labeled graphs on $4$ vertices can be partitioned into isomorphism classes, and the question asks to draw one graph from each isomorphism class.

To answer your question, ignore labelings on vertices, and first draw all graphs on $4$ vertices containing exactly $0$ edges (there is only one such graph), then all graphs containing exactly $1$ edge (there is only one such graph), all graphs containing exactly $2$ edges (there are 2 such graphs, because the two edges can be incident or independent), etc. And you get that the total number of pairwise nonisomorphic graphs on $4$ vertices is $1+1+2+3+2+1+1 = 11$.