In a connected graph G degrees of four vertices are equal to

In a connected graph G degrees of four vertices are equal to 3, degrees of all other vertices are equal to 4. Prove that if for some edge e, G - e is disconnected, components of G-e cannot be isomorphic. Show proof

Solution

we are given that

in a connected graph G the no of degree of 4 vertex is 3 and all other vertex degree is 4

let us suppose the no of vertex with degree 4 is 3

then the degree sequence will be in decreasing order is

(4,4,4,3,3,3,3)

when you will try to draw a graph with the given degree sequence, you will not be able to draw a graph means graph is disconnected.

(you may take any no of vertex with degree 4,you will see that graph is disconnected ,when you will draw the graph with that degree sequence)

for graph to be isomorphic, the very first condition is that the degree sequence of both the graph should be in same sequence after rearranging (either increasing or decreasing)

but in this case we can notice that degree sequence cannot be same , so the given graph will not be isomorphic