Isomorphism of All Simple Graphs with 5 Vertices and 9 Edges

discrete mathematicsgraph theory

Given the simple graph H with vertex set {a,b,c,d,e} and nine edges consisting of all possible edges except edge {c,e}. Are all simple graphs with five vertices and nine edges isomorphic to H? Why?

I tried solving this by checking every permutation and I think the answer is yes, but my question really is, how can we explain or prove this?

Best Answer

If $G$ is a simple graph with five vertices, say $v_1,v_2,v_3,v_4,v_5$, and nine edges, then it has all edges except $v_iv_j$ for some values $i,j$. $H$ is isomorphic to $G$ because you can map $c$ to $v_i$, $e$ to $v_j$, and $a,b,d$ to the other three vertices in some order.