this is edge counting problemhelp me please Attempt the foll

this is edge counting problem....help me please!

Attempt the following problems and write your answer in the blue book provided. Show all steps and arguments clearly for partial credit. What is the largest number of vertices in a graph G =(V,E) with 28 edges three vertices are of degree 2 and all other vertices are of degree at least 3? just, your answer! What is the least number of vertices that a simple graph G = (V, E) with edges can have? Justify your answer! Determine whether the following two graphs are isomorphic.

Solution

(a)

Let number of vertices be m

Let total number of edges be e

Hence, 2e=sum of degrees of vertices

Hence for given problem:

2e>=3*2+(m-3)3=3m-3

3m<=2e+3

3m<=59

m<=59/3

Hence, largest number of vertices is 19

(b)

Since graph is simple so there cannot be more than one edge between two vertices.

For least number of vertices we must maximise degree of each vertex.

This is possible only in a graph.

In a complete graph with n vertices number of edges are: n(n-1)/2

n(n-1)/2=70

Solving for n gives:n=12.343

So we can have a complete graph with 12 vertices giving: 12*11/2=66 edges.

And add one more vertex which connect to 4 other edges of this complete graph giving us: 13 vertices and 70 edges.

So 13 is the least number of vertices possible with 70 edges.