I am being asked to show that the following two graphs are notisomorphic by supp

Question

I am being asked to show that the following two graphs are notisomorphic by suppossing they are isomorphic and deriving acontradiction.
Then they give me the two graphs. however i cannot solve this?

Explanation / Answer

suppose that g and g' are isomorphic via 1-1 correspondences g:v(g) -> v(g') and h: e(g) -> e(g'), where g and h preservethe edge-endpoint functions. now w6 has degree one ing', and so b y argument given in example 11.4.4, w6 mustcorrespond to one of the vertices of degree one in g: eitherg(v1) = w6 or g(v6) =w6. similarly, since w5 has degree 3 in g',w5 must correspond to one of the vertices of degree g:either g(v3) = w5 or g(v4) =w5. because g and h preserve the edge-endpointv1 and v3, or v1 andv4, or v6 and v3, or v6and v4. but this contradicts the fact that non of thesepairs of vertices are connected by edges in g. hence thesupposition if false, and g and g' are not isomorphic.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.