0
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ Consider that you arrive at $H$ by deleting one edge from $K_5$ $\endgroup$ – saulspatz Nov 30 '20 at 15:51
  • $\begingroup$ Is this connected to Kuratowski's Theorem? $\endgroup$ – muw Nov 30 '20 at 16:00
  • 1
    $\begingroup$ The only connection between this and Kuratowski's theorem is that both involve $K_5$. Kuratowski's theorem is considerably deeper than this. $\endgroup$ – Andreas Blass Nov 30 '20 at 16:46
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

Suppose you have two copies of $K_5$. They're obviously isomorphic, and in fact, every bijection between the vertices is an isomorphism. Now remove and edge from edge graph. The two resulting graphs are isomorphic, because there was an isomorphism of the $K_5$ that carried the vertices of one of the removed edges to the vertices of the other.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.