Example 4.4.5 Let $V=\{1,2,3,4\}$, find the number of non-isomorphic graphs of order 4 with $V$ as the vertex set.
Let $S_{4}$ be the set of all 4-vertex graphs with vertex set $V=\{1,2,3,4\}$. The edge set $E_{1}$ of a graph $H_{1}=\left(V, E_{1}\right)$ in $S_{4}$ is a subset of $X=\{\{1,2\},\{1,3\},\{1,4\},\{2,3\},\{2,4\}, \{3,4\}\}$.

We can view $H_{1}$ as a coloring of the edges in set $X$ with two colors “yes” $(y)$ or “no” $(n)$, where the edges in $E_{1}$ are colored $y$, and the edges not in $E_{1}$ are colored $n$. Let $C$ be the set of all colorings of $X$ using $y$ and $n$. Therefore, the graphs in $S_{4}$ are exactly the colorings in $C$.

Let $H_{2}=\left(V, E_{2}\right)$ be another graph in $S_{4}$. Then $H_{1}$ and $H_{2}$ are isomorphic if and only if there exists a permutation $\sigma$ of $V=\{1,2,3,4\}$ such that $\{i, j\} \in E_{1} \Leftrightarrow\{\sigma(i), \sigma(j)\} \in E_{2}$.

Let $G$ be the set of all 24 permutations of $V=\{1,2,3,4\}$. For each $\sigma \in G$, we can use the rule $\{i, j\} \rightarrow\{\sigma(i), \sigma(j)\}(\{i, j\} \in X)$ to permute the edges in $X$.
For example, $\sigma=\left(\begin{array}{llll}1 & 2 & 3 & 4 \\ 3 & 2 & 4 & 1\end{array}\right)$, then $\sigma$ permutes the edges in $X$ as follows:

i.e., $\quad\left(\begin{array}{llllll}\{1,2\} & \{1,3\} & \{1,4\} & \{2,3\} & \{2,4\} & \{3,4\} \\ \{3,2\} & \{3,4\} & \{3,1\} & \{2,4\} & \{2,1\} & \{4,1\}\end{array}\right)$,
Let $G^{(2)}$ be the permutation group of $X$ obtained in this way from $G$. Then two graphs $H_{1}, H_{2}$ in $S_{4}$ are isomorphic if and only if, as colorings of $X$, they are equivalent. The number of non-isomorphic graphs in $S_{4}$ is converted to the number of non-equivalent colorings in $C$ under the permutation group $G^{(2)}$, denoted as $N\left(G^{(2)}, C\right)$. To achieve this, we must calculate the cycle types of the 24 permutations in $G^{(2)}$. The calculation results are listed in the table below:
\begin{tabular}{|c|c|c|}
\hline Type & Polynomial & Number of permutations in $G^{(2)}$ \\
\hline $1^{6}$ & $x_{1}^{5}$ & 1 \\
\hline $1^{2} 2^{2}$ & $x_{1}^{2} x_{2}^{2}$ & 9 \\
\hline $3^{2}$ & $x_{3}^{2}$ & 8 \\
\hline $2^{1} 4^{1}$ & $x_{2} x_{4}$ & 6 \\
\hline
\end{tabular}

The generating function $P_{G^{(2)}}\left(x_{1}, x_{2}, x_{3}, x_{4}, x_{5}, x_{6}\right)=\frac{1}{24}\left(x_{1}^{6}+9 x_{1}^{2} x_{2}^{2}+8 x_{3}^{2}+6 x_{2} x_{4}\right)$.
$$
\begin{array}{l} 
P_{G^{(2)}}\left(y+n, y^{2}+n^{2}, y^{3}+n^{3}, y^{4}+n^{4}, y^{5}+n^{5}, y^{6}+n^{6}\right) \\
= \frac{1}{24}\left[(y+n)^{6}+9(y+n)^{2}\left(y^{2}+n^{2}\right)^{2}+8\left(y^{3}+n^{3}\right)^{2}+\right. \\
\left.6\left(y^{2}+n^{2}\right)\left(y^{4}+n^{4}\right)\right] \\
= y^{6}+y^{5} n+2 y^{4} n^{2}+3 y^{3} n^{3}+2 y^{2} n^{4}+y n^{5}+n^{6}, \\
N\left(G^{(2)}, C\right)=P_{G^{(2)}}(2,2,2,2,2,2)=11 .
\end{array}
$$

Note that the power of color $y$ equals the number of edges. Thus, the number of non-isomorphic 4-vertex graphs with various numbers of edges is given by the table below:
\begin{tabular}{|c|c|}
\hline Number of edges & Number of non-isomorphic graphs \\
\hline 6 & 1 \\
\hline 5 & 1 \\
\hline 4 & 2 \\
\hline 3 & 3 \\
\hline 2 & 2 \\
\hline 1 & 1 \\
\hline 0 & 1 \\
\hline
\end{tabular}
There are 11 non-isomorphic 4-vertex graphs. These 11 graphs can be drawn as follows: