Question

please throughly explain each step.

47.21. What does it mean for two graphs to be the same? Let G and H be graphs. We say th G is isomorphic to H provided there is a bijection f VG)-V(H) such that for all a, b e 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: v E V(G), then the degree of v in G equals the degree of f(v) in H number of edges but that are not isomorphic. edge from v to w if and only if v - w is odd. Let H be the graph in the figure. 

a. Prove that isomorphic graphs have the same number of vertices. 

b. Prove that if f : V(G) → V(H) is an isomorphism of graphs G and H and it c. Prove that isomorphic graphs have the same number of edges. d. Give an example of two graphs that have the same number of vertices al and the same and the same be the graph whose vertex set is 1.2,3,4,5,6. In this graph, there e. Let G Find an isomorphism f : V(G) V(H).

Answer 1

Solution:

47.21

a)

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

we need a bijection f: V→V′ 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 e∈V 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 −

• Their number of components (vertices and edges) are same.
• Their edge connectivity is retained.

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

Two graphs that have the same number of vertices and the same number of edges but are not isomorphic

e). graph of H is: