What does it mean for two graphs to be the same? Let G and H be graphs. We Say t

Question

What does it mean for two graphs to be the same? Let G and H be graphs. We Say that G is isomorphic to H provided there is a bijection f : V(G) rightarrow V(H) such that for all a middot b epsilon V(G) we have a~b (in G) if and only if f(a) ~ f(b) (in H). The function f is called an isomorphism of G to H. We can think of f as renaming the vertices of G with the names of the vertices in H in a way that preserves adjacency. Less formally, isomorphic graphs have the same drawing (except for the names of the vertices). Please do the following: Prove that isomorphic graphs have the same number of vertices. Prove that if f : V(G) rightarrow V(H) is an isomorphism of graphs G and H and if upsilon epsilon V(G), then the degree of upsilon in G equals the degree of f(upsilon) in H. Prove that isomorphic graphs have the same number of edges. Give an example of two graphs that have the same number of vertices and the same number of edges but that are not isomorphic. Let G be the graph whose vertex set is {1, 2, 3, 4, 5, 6}. In this graph, there is an edge from upsilon to omega if and only if upsilon - omega is odd. Let H be the graph in the figure. Find an isomorphism f : V(G) rightarrow V(H).

Explanation / Answer

a)

A graph with zero number of edges won't be isomorphic so it should be like

we need a bijection f: VV with {v1,v2}E iff {f(v1),f(v2)}E

. Now give an explicit bijection

f: V1 V2,

and show that if {e1,e2}E1, then {f(e1),f(e2)}E2

.

Checking that Deg(e)=Deg(f(e))

for all eV is not sufficient: Given an isomorphism f, we obtain another bijection g: V1 V2 by switching U and W, that is;

                     W     if f(e)=U

     g(e) =               U      if f(e)=W

                            f(e)    otherwise

b),c)

Two graphs G and H are said to be isomorphic if

Suppose the graph G has n vertices with degrees d1,d2,....dn

Add together all these degrees to get a new number

d1+d2+....dn=Dv then

Dv=2e ie,

for any graphs the sum of the degrees of vertices equals the twice the number of edges.

d)

Suppose two graph with vertices and edges like

first graph has vertices like {a,b,c,d} and has edges from a-b,a-d,a-c,c-d

second graph has vertices like{1,2,3,4} and has edges from 1-2,1-3,3-4,2-4

but these two graphs are not isomorphic even though they have equal number of vertices and edges because

the first graph has a vertex with degree 3 but the second graph doesn't have a vertex with degree 3

       

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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