0
$\begingroup$

I'm reading Richard J. Trudeau's book "Introduction to Graph Theory", in ch 2 there's an example

Example. The graphs of Figure 35
Fig 35 are not isomorphic, even though they share the four properties: in each v = 8 and e = 10; each has four vertices of degree 2 and four of degree 3; and they are both in one piece. The structural difference is that the vertices of degree are not related in the same way in the two graphs. In the first graph the vertices of degree 2 come in adjacent pairs: B is adjacent to H and D is adjacent to F. But in the second graph they are completely separated from one another by vertices of degree 3: no vertex of degree is adjacent to any other vertex of degree 2. To see how this prevents the graphs from being isomorphic, we shall systematically try to construct an isomorphism in all possible ways. We begin by noticing that B, being of degree 2, would have to correspond to 1, 3, 6, or 8.

First case: B corresponds to 1.

Then H, being adjacent to B, would have to correspond to 2 or 7. But H must correspond to a vertex having the same degree, so H cannot correspond to either 2 or 7. Therefore no isomorphism is possible if B is made to correspond with 1.

Second case: ...

after discussed all 4 cases, it announces

We have seen that no isomorphism is possible if B is made to correspond to any of 1, 3, 6, or 8. But under any isomorphism, B would have to correspond to 1, 3, 6, or 8. Therefore no isomorphism is possible, and the graphs of Figure 35 are not isomorphic.

I agree with all the proof process, just, I wonder, is it enough to assert being not isomorphic via connectivity of vertices of certain degrees? Such as, with such differences

In the first graph the vertices of degree 2 come in adjacent pairs... But in the second graph they are completely separated from one another by vertices of degree 3

is it ok to announce the two graphs are not isomorphic? Is there a such general theorem?

$\endgroup$
1
$\begingroup$

Yes, it is sufficient. For a graph $G$, let $G_d$ be the induced subgraph made by vertices of degree $d$. We have the following

Lemma: suppose $f:G \to H$ is an isomorphism of graphs. Then $f| G_d :G_d \to H_d$ is an isomorphism for every $d$.

Indeed, $f$ maps vertices of degree $d$ to vertices of degree $d$: the neighbors of $f(v)$ are exactly $\{f(w)\}$ where $w$ is a neighbor of $w$. So $f|G_d : G_d \to H_d$ is injective and surjective on vertices: injective because it is the restriction of an injective map, surjective because every vertex of degree $d$ must be taken by a vertex of degree $d$. Moreover, for $v,w \in G_d$: $$(v,w) \in G_d \ \ \Leftrightarrow \ \ (v,w) \in G \ \ \Leftrightarrow \ \ (f(v),f(w) ) \in H \ \ \Leftrightarrow \ \ (f(v),f(w) ) \in H $$ using the property that $f$ is an iso and that $G_d, H_d$ are induced subgraphs.

In your case, set $G$ the graph on the left, $H$ the graph on the right. You have that $G_2$ has two connected components, while $H_2$ has four connected components, so they cannot be isomorphic.

$\endgroup$
  • $\begingroup$ How are edges in $G$ picked up to form &G_d$? $\endgroup$ – athos Oct 12 at 17:04
  • 1
    $\begingroup$ Induced subgraph means: take the prescribed vertices, with all the edges between them that comes from the big graph. In symbols $(v,w) \in G_d$ iff $(v,w) \in G$, for $v,w \in G_d$. $\endgroup$ – Andrea Marino Oct 12 at 17:08

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.