I need a pair of non-isomorphic graphs with the smallest n-vertex possibility and where degree sequences are the same. Is the minimum number 2, such as a multigraph with n=2? Please help with the reasoning on this question. Thank you!
The smallest $n$ for which loopless graphs contain non-isomorphic $n$-vertex graphs with the same degree sequence
graph theory
Best Answer
For $n=5$, there are three pairs of simple graphs that have the same degree sequence:
For $n=4$, there are no simple graphs that work (which we can verify by checking all $11$ possibilities). If loopless multigraphs are fair game, then the cycle $C_4$ can be confused with the disjoint union of two digon graphs (where a digon graph has two vertices with two copies of the edge between them); other examples also exist.
For $n=3$ and under, not even parallel edges help. In the $n=1$ case, there is only one loopless multigraph. In the $n=2$ case, our only freedom is choosing the number of edges between the two vertices, and that number of edges also tells us the degree of each vertex. In the $n=3$ case, if the degree sequence is $d_1, d_2, d_3$, and there are $m_{ij}$ edges between vertices $i$ and $j$, then we have the system of equations \begin{align} d_1 &= m_{12} + m_{13} \\ d_2 &= m_{12} + m_{23} \\ d_3 &= m_{13} + m_{23} \end{align} and this has a unique solution when $d_1, d_2, d_3$ are fixed: $$(m_{12}, m_{13}, m_{23}) = \left(\frac{d_1 + d_2 - d_3}{2},\frac{d_1 - d_2 + d_3}{2},\frac{-d_1 + d_2 + d_3}{2}\right).$$ Therefore there at most only one loopless multigraph with each degree sequence. (Some degree sequences won't produce any loopless multigraph, if the degrees are odd, or if one degree exceeds the sum of the other two.)