Can we conclude that $G_1 \not ≅ G_2$?

83 Views Asked by At

I'm working in the following graph theory excercise:

Let $G_1$ and $G_2$ be two graphs with $V(G_1) = {u_1, v_1, w_1, x_1, y_1, z_1}$ and $V(G_2) = {u_2 , v2_ , w_2 , x_2 , y_2 , z_2}$. If $v_1$ has degree $3$ and is adjacent to a vertex of degree $2$, while $v_2$ has degree $3$ and is not adjacent to a vertex of degree $2$. Can we conclude that $G_1 \not ≅ G_2$? Explain your answer.

What I think about the answer is that obviously because of adjacent vertices to $v_1$ and $v_2$ are not the same then $G_1 \not ≅ G_2$ but I'm not sure about it to be so obvious, thanks in advance for any critic to my solution, a hint or help.

1

There are 1 best solutions below

0
On BEST ANSWER

Consider the following graph on 6 vertices.

A-----B
|     |
|     |
C-----D
 \   /
  \ /
   E
   |
   |
   F

Notice that vertices $A$ and $B$ have degree $2$, vertices $C$, $D$, and $E$ have degree $3$, and vertex $F$ has degree $1$. Vertices $C$ and $D$ are each adjacent to a vertex with degree $2$, but vertex $E$ is not adjacent to any vertex with degree $2$.

Can you use this to generate two isomorphic graphs $G_1$ and $G_2$ with all the properties in the question?