Common neighbour in graph where all cycles are chordless

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

Common neighbour in graph where all cycles are chordless

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: 2024 Macedonian Balkan Math Olympiad TST Problem 1

The post below has been deleted. Click to close.

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

351 posts

#1 h Apr 21, 2024, 11:38 PM • 1 Y

Y by GeoKing

In a given group of people $\mathcal{F}$ , each member has at least two acquaintances from $\mathcal{F}$ . Moreover, for each cycle $A_{1} \leftrightarrow A_{2} \leftrightarrow ... \leftrightarrow A_{n} \leftrightarrow A_{1}$ in $\mathcal{F}$ (here ' $X \leftrightarrow Y$ ' means that $X$ and $Y$ are acquaintances), each $A_i$ knows exactly two other members $A_j$ of the cycle. Prove that there exist $X, Y \in \mathcal{F}$ such that each of them has exactly two acquaintances in $\mathcal{F}$ , and $X, Y$ have at least one common acquaintance in the group.

Authored by Mirko Petrusevski

This post has been edited 2 times. Last edited by steppewolf, Feb 9, 2025, 10:35 PM

Z K Y

The post below has been deleted. Click to close.

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

874 posts

#2 h Apr 22, 2024, 1:14 AM

Y by

misread problem

This post has been edited 1 time. Last edited by sami1618, Apr 22, 2024, 6:55 PM

Z K Y

The post below has been deleted. Click to close.

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

1260 posts

#3 h Apr 22, 2024, 6:42 PM • 1 Y

Y by GeoKing

EDIT: Didn't realize non-leaves could have back edges :wallbash:

:wallbash:

Anyway the proof should be correct now.

Take the obvious graph $G$ . WLOG assume $G$ is connected, else look at a connected component. The given condition implies that every cycle is chordless. Do DFS from a random vertex to get a spanning tree $T$ . Note that every back edge in a DFS is from a vertex to an ancestor of the vertex. By the chordless condition, every vertex has at most one back-edge starting at that vertex, and since every degree is at least $2$ , every leaf has exactly one back-edge, i.e., every leaf has degree exactly two. For any $u_1,u_2$ , let $P(u_1,u_2)$ denote the unique path from $u_1$ to $u_2$ in $T$ .

For any leaf $l$ , let $f(l)$ denote the other endpoint of the back-edge at $l$ , and let $g(l)$ be the first vertex after $f(l)$ in the path from $f(l)$ to $l$ in $T$ . Clearly $g(l) \neq l$ . Choose a leaf $l$ such that $f(l)$ is furthest away from the root. We claim that $g(l)$ has degree $2$ . We will then be done, as $l$ and $g(l)$ have a common neighbor $f(l)$ . Since $g(l)$ already has two edges: One going to $f(l)$ , and one going along the path from $g(l)$ to $l$ . We have to show that there are no other edges. Let $C$ be the cycle consisting of the path in $T$ from $f(l)$ to $l$ , and the back-edge from $l$ to $f(l)$ .

We first show that degree of $g(l)$ in $T$ is $2$ , i.e., there are no other branches at $g(l)$ . Assume the contrary; then there is a leaf $l' \neq l$ that is a descendent of $g(l)$ along the other branch. $f(l')$ is closer to the root than $f(l)$ , by our given condition. Then $f(l)g(l)$ is a chord in the cycle $P(f(l'),f(l))f(l)lP(l,g(l))P(g(l),l')l'f(l')$ , contradiction!

Now we analyze back-edges at $g(l)$ . First, suppose there is a back-edge starting at $g(l)$ . The other end, $u$ , must be an ancestor of $f(l)$ . But then, $f(l)g(l)$ is a chord in the cycle $g(l)uP(u,f(l))f(l)lP(l,g(l))$ , contradiction!

Finally, suppose some back-edge $ug(l)$ ends at $g(l)$ . $u$ cannot be in $C$ as $C$ is chordless, so $u$ cannot be an ancestor of $l$ . $u$ cannot be a leaf, as then $f(u)=g(l)$ is further away from the root than $f(l)$ . Hence $u$ has a leaf descendent, say $l'$ . Note that $f(l)$ is an ancestor of $l'$ , so again by the condition on $l$ , $f(l')$ must be an ancestor of $f(l)$ , which is an ancestor of $g(l)$ . But then, $g(l)u$ is a chord in the cycle $l'f(l')P(f(l'),l')$ , contradiction!

Hence we get a contradiction in every case, so degree of $g(l)$ is $2$ , as required.

This post has been edited 2 times. Last edited by Supercali, Apr 26, 2024, 10:29 AM
Reason: big mistake

Z K Y

The post below has been deleted. Click to close.

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

663 posts

#4 h May 4, 2024, 6:54 PM

Y by

https://artofproblemsolving.com/community/c6h3313173p30606863

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a