Finding a Star of Equal Degrees

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Finding a Star of Equal Degrees

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: Iranian Combinatorics Olympiad P4

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

499 posts

#1 h Apr 25, 2020, 2:13 PM • 1 Y

Y by moom

Given a graph with $99$ vertices and degrees in $\{81,82,\dots,90\}$ , prove that there exist $10$ vertices of this graph with equal degrees and a common neighbour.

Proposed by Alireza Alipour

This post has been edited 3 times. Last edited by matinyousefi, Apr 27, 2020, 12:52 PM
Reason: Typo

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

4071 posts

#2 h Apr 27, 2020, 1:27 PM • 1 Y

Y by aaabc123mathematics

It is impossible for every vertex to have degree $81$ , because it would imply the sum of all degrees is odd.
Suppose to the contrary that there doesn't exist such $10$ vertices.
Let $v$ be a vertex with degree more than $81$ . Consider $N(v)$ , the set of neighbors of $v$ .
For each $k\in \{ 81,82,\dotsc , 89\}$ , at most $9$ vertices of degree $k$ belong to $N(v)$ .
Since $|N(v)|>9\cdot 9$ , there exists a vertex in $N(v)$ that has degree $90$ . Call this vertex $w$ .
Consider $N(w)$ , the set of neighbors of $w$ .
By a similar argument $N(w)$ must contain exactly $9$ vertices of degree $k$ for each $k\in \{ 81,82,\dotsc ,90\}$ .
Hence, there are at least $10$ vertices that have degree $90$ . We claim that they constitute the desired $10$ vertices.
For each vertex $u$ of the $10$ vertices, the number of vertices that are not neighbor of $u$ is equal to $9$ .
Hence, there exist at least $99-10\cdot 9>1$ vertices that are neighbor of all of them.

This post has been edited 1 time. Last edited by ThE-dArK-lOrD, Apr 27, 2020, 1:29 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

65 posts

Arefe

#3 h May 9, 2020, 10:00 AM

Y by

Suppose that we have a vertex with degree $90$ , name it $A$ .
$X_i$ be the set of all vertex with degree $i$ .
If in middle of $A$ 's neighbors we have at least $10$ member of one of the $X_i$ the problem is proved .
So we have at most $9$ members of every $X_i$ , because we have $10$ sets and degree of $A$ is $90$ , so every $X_i$ have exactly $9$ members and now we have $9$ vertex with degree $90$ in middle of $A$ 's neighbors so because we have $99$ vertex at all so we have $X_j$ such that $|X_j|<10$ so every member of $X_j$ are neighbor of all the member of $X_{90}$ and the problem is proved .
So suppose that $|X_{90}|=0$ and at least one of the $X_{82}$ , … , $X_{89}$ isn't empty . Give $B$ one of the member of that set .
$B$ has at least $82$ neighbors and we have at most $9$ set so we can find at least $10$ member of one of the $X_i$ and the problem is proved .
The last situation is when all of the vertexes are of degree $81$ and the problem is obviously proved .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

579 posts

#4 h Jul 26, 2021, 10:19 PM

Y by

Let $x_k$ be the number of nodes with degree $k$ . Then, we double count the number of pairs $(A,B)$ where $\text{deg }B = k$ . This, gives by comparing choosing $A$ first vs. choosing $B$ first,
$k\cdot a_k = \# \text{ of } (A,B) \leq 99\cdot 9$ Thus, $a_{81}\leq 11$ , for $82\leq m \leq 89$ , $a_m \leq 10$ , and $a_{90}\leq 9$ . Thus,
$99 = \sum_{k=1}^{90} a_k \leq 11+8\cdot 10 + 9 = 100$ Therefore, all $a_k$ bounds are strict, with one exception which is exactly one lower than the bound. Thus, there must be a node with degree 90, call it $P$ . Additionally, note that
$\sum_{k=1}^{89} |a_k-9| = \sum_{k=1}^{89} (a_k-9) = (99-a_{90}) - 9\cdot 9 \geq 9$ Thus, since $P$ is connected to all but 8 nodes, there exists some $k$ such that $P$ has less than $|a_k-9|$ missed nodes to $a_k$ , which is equivalent to $P$ having 10 edges going to $a_k$ , and we have proved existence. $\blacksquare$ .

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a