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.

Solution

here we are given that

in a connected graph degree of 4 vertex is 3 and all other vertex have degree is 4

let the no of vertex with degree be =4, then

degree sequence will be (decreasing) is

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

now with this given degree sequence ,when we will try to draw a graph, we will not able to draw a connected graph

means graph will be disconnected(you wil notice this after moving 3rd or 4th step)

you can assume any no vertex with degree 4,you will see that connected graph is not possible.

and for graph to be isomorphic

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

but for the given degree sequence when we will draw a disconnected graph the degree sequence will never be same ,so the with the given degree sequence the graph can not be isomorphic.