(a) Show that 2, 3, 3, 3 is not the eccentricity sequence of any graph. (b)...

for any two vertex p and q in a connected graph G let d(a,b) denote the distance between p and q.

(a) Let G be a connected graph of order 4 having a vertex u with eccentricity 2. Then there are vertices v and w. Such that u and w are not adjacent and is a path. Let x be the vertex of G other than u, v and w. Since w must have eccentricity 3, and d(w,v)=1 and d(w,u)= 2, x must be adjacent to u and not adjacent to v and is a path.

But then v cannot have eccentricity 3 as its distance from any other vertex is less than 3

(b).Let G be a graph with eccentricity sequence a,b,b,b where a<b are positive integers.Since the eccentricity sequence has 4 elements G is a connected graph of order 4. Therefore we must have both a and b < 4 as the length of a path in a conncected graph is less than the order of the graph . Therefore and .

if a= 2 then b= 3 and we cannot have a graph in this case by the solution of the previous problem.

if a=1 then there is a vertex v of G such that d(v,s)=1 for all other vertex s of G. Thus the other 3 vertices are adjacent to v. and hence we must have b=2.

We give an example of such a graph example below