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
    Commented Nov 30, 2020 at 15:51
  • $\begingroup$ Is this connected to Kuratowski's Theorem? $\endgroup$
    – muw
    Commented Nov 30, 2020 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$ Commented Nov 30, 2020 at 16:46

2 Answers 2

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .