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
Source: Iran Team selection test 2024 - P1
Tags: combinatorics
19.05.2024 19:19
The answer is $\boxed{4}$: Construction: Consider the following graph where the blue vertex has two neighbors and the ten green vertices have three neighbors. Notice that the distance in between the blue vertex and the top green vertex on the inner layer is $4$. Now we verify this graph satisfies the condition involving sub-graphs $A$. The case $|A|=2$ is obvious. Now assume $2< |A|\leq 4$. If their exists vertices from $A$ that lie on both pentagons then there will be at least two boundary points belonging to each pentagon hence $A$ has at least $4$ neighbors. The cases were all the vertices of $A$ lie on one pentagon can be easily verified. [asy][asy] draw((0,2)--(2,0)); draw((2,0)--(1,-2)); draw((1,-2)--(-1,-2)); draw((-1,-2)--(-2,0)); draw((-2,0)--(0,2)); draw((0,4)--(4,0)); draw((4,0)--(2,-4)); draw((2,-4)--(-2,-4)); draw((-2,-4)--(-4,0)); draw((-4,0)--(0,4)); draw((0,2)--(0,4)); draw((2,0)--(4,0)); draw((1,-2)--(2,-4)); draw((-1,-2)--(-2,-4)); draw((-2,0)--(-4,0)); filldraw(circle((0, 2), 0.2), green, red); filldraw(circle((2, 0), 0.2), green, red); filldraw(circle((-2, 0), 0.2), green, red); filldraw(circle((1, -2), 0.2), green, red); filldraw(circle((-1, -2), 0.2), green, red); filldraw(circle((0, 4), 0.2), green, red); filldraw(circle((4, 0), 0.2), green, red); filldraw(circle((-4, 0), 0.2), green, red); filldraw(circle((2, -4), 0.2), green, red); filldraw(circle((-2, -4), 0.2), green, red); filldraw(circle((0, -4), 0.2), blue, red); [/asy][/asy] Bound: We will prove that from each vertex of degree $3$ we can reach all other vertices in at most $4$ moves. In at most $1$ move we can reach $4$ vertices. By the conditions of the problem, in at most $2$ moves we can reach more than $8$ vertices. Then it is not hard to show that it will take it most $2$ moves to reach all of the remaining vertices.
19.05.2024 20:10
redacted,read wrong the statement
19.05.2024 20:28
Answers above are incorrect , you just proved that for any proper graph $G$ , there exist two vertices with distance $3$ and also the answer is actually $4$. For constructing a proper graph with diameter $4$ , consider a circle with vertices $v_1 , v_2 , v_3 , v_4 , v_5 , v_6$ and another one with vertices $w_1 , w_2 , w_3 , w_4 , w_5$ and also connect pairs $v_1 , w_1$ and $v_2 , w_2$ and $v_3 , w_3$ and $v_5 , w_4$ and $v_6 , w_5$.
19.05.2024 20:47
wait, do we have to find the maximum or the minimum diameter ? @below: sorry
19.05.2024 20:50
motannoir wrote: wait, do we have to find the maximum or the minimum diameter ? The problem statement asks for the maximum!
19.05.2024 21:13
Shayan-TayefehIR wrote: motannoir wrote: wait, do we have to find the maximum or the minimum diameter ? The problem statement asks for the maximum! Understood, when it was posted before it asked for the minimum I will fix my solution.