MathDB

Let

G

be a simple graph with

11

vertices labeled as

v_{1} , v_{2} , ... , v_{11}

such that the degree of

v_1

equals to

2

and the degree of other vertices are equal to

3

.If for any set

A

of these vertices which

|A| \le 4

, the number of vertices which are adjacent to at least one verex in

A

and are not in

A

themselves is at least equal to

|A|

, then find the maximum possible number for the diameter of

G

. (The distance between two vertices of graph is the number of edges of the shortest path between them and the diameter of a graph , is the largest distance between arbitrary pairs in

V(G)

. )
Proposed by Alireza Haqi

Problem Statement