IMO ShortList 2001, combinatorics problem 3

The post below has been deleted. Click to close.

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

orl

3647 posts

orl

#1 h Sep 30, 2004, 5:26 PM • 3 Y

Y by Purple_Planet, Adventure10, Mango247

Define a $k$ -clique to be a set of $k$ people such that every pair of them are acquainted with each other. At a certain party, every pair of 3-cliques has at least one person in common, and there are no 5-cliques. Prove that there are two or fewer people at the party whose departure leaves no 3-clique remaining.

Attachments:

This post has been edited 2 times. Last edited by orl, Dec 22, 2008, 1:12 AM

Z K Y

The post below has been deleted. Click to close.

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

orl

3647 posts

orl

#2 h Sep 30, 2004, 5:26 PM • 2 Y

Y by Adventure10, Mango247

Please post your solutions. This is just a solution template to write up your solutions in a nice way and formatted in LaTeX. But maybe your solution is so well written that this is not required finally. For more information and instructions regarding the ISL/ILL problems please look here: introduction for the IMO ShortList/LongList project and regardingsolutions

Z K Y

The post below has been deleted. Click to close.

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

grobber

7849 posts

grobber

#3 h Oct 25, 2004, 8:47 AM • 5 Y

Y by narutomath96, Purple_Planet, Adventure10, Mango247, and 1 other user

I'd love to see another solution..

It's clearly impossible to have more than two triangles s.t. each two have a common edge, so count this case out. Take two triangles $xyz,xuv$ s.t. $\{x,y\}\cap\{u,v\}=\emptyset$ . Assume first that all of our triangles which don't have $x$ as a vertex have their vertices among $y,z,u,v$ . There must be such a triangle which doesn't have $y$ as a vertex, and the same holds for $z,u,v$ , so $xyzuv$ is a $K_5$ , which can't be true. This means that among the triangles which don't have $x$ as a vertex, we can find one $tvz$ (for example) s.t. $t\notin\{x,y,z,u,v\}$ .

Assume now that the conclusion doesn't hold. This means that we can find triangles which don't have $(x,v),(v,x)$ or $(z,x)$ as vertices. After noticing that $yu,ut,ty$ can't be edges, we can see that the only way this can happen is to have another vertex $p$ and triangles $pxt,pyv,puz$ . This, however, means we have the $K_5$ $xyzvp$ , a contradiction.

Z K Y

The post below has been deleted. Click to close.

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

DusT

297 posts

DusT

#4 h Oct 28, 2004, 4:43 PM • 2 Y

Y by Adventure10, Mango247

This IS almost like the oficial solution. I mean, it is I think the only solution.

Z K Y

The post below has been deleted. Click to close.

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

orl

3647 posts

orl

#5 h Oct 28, 2004, 5:14 PM • 3 Y

Y by AlastorMoody, Adventure10, Mango247

DusT wrote:

This IS almost like the oficial solution. I mean, it is I think the only solution.

Well, I don't see the problem if grobber comes up with the same idea as in the official solution. Dust, there are still lots of other unsolved ISL problems on the forums. Go and solve them if you want to have a gold medal at the next IMO in Mexico.

Z K Y

The post below has been deleted. Click to close.

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

Zhero

2043 posts

Zhero

#6 h Jul 23, 2010, 11:11 PM • 1 Y

Y by Adventure10

Suppose for the sake of contradiction that the result is false. First, I will show that no two triangles can share an edge.

Suppose we have distinct triangles $ABC$ and $BCD$ sharing edge $BC$ . If we remove $B$ and $C$ , there must remain another triangle. This triangle clearly cannot have all of its vertices among $A,B,C,D$ , so we can find some point $E$ distinct from $A,B,C,D$ belonging to a triangle. This 3-clique must not be disjoint with either $ABC$ or $BCD$ , yet it cannot contain $B$ or $C$ , so it must contain $A$ and $D$ . Hence, $AD$ , $DE$ , and $EA$ are connected.

Suppose that upon removing $A$ and $D$ , there still exists a 3-clique. It cannot be disjoint with triangle $ADB$ , $ADC$ , or $ADE$ , yet it cannot contain either $A$ or $D$ , so it must contain $B$ , $C$ , and $E$ . It follows that $B$ , $C$ , and $E$ are connected, so $ABCDE$ is a 5-clique, which is a contradiction. Therefore, no two triangles can share an edge.

If we have one 3-clique, the result is trivial. If we have two 3-cliques, they may share only one vertex, say, $P$ ; in the first 3-clique, let the other two vertices be $Q$ and $R$ , and in the second, let the other two vertices be $S$ and $T$ . When $P$ and $R$ are removed, there exists a 3-clique among the remaining vertices. It cannot be among $Q$ , $T$ , and $S$ , or else triangles $PQT$ and $QST$ will share edge $QT$ , so there exists another vertex $U$ belonging in this 3-clique. This 3-clique cannot be disjoint with $PQR$ , and it cannot contain $P$ and $R$ , so it must contain $Q$ . It is not disjoint with $PST$ , so it must contain one of $S$ and $T$ ; without loss of generality, suppose it contains $S$ . But then we have triangles $PQS$ and $QUS$ sharing edge $QS$ , so we have reached a contradiction.

Z K Y

The post below has been deleted. Click to close.

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

riemannHypothesis2.71828

79 posts

riemannHypothesis2.71828

#7 h Jan 23, 2011, 5:02 AM • 4 Y

Y by TheEpicCarrot7, Adventure10, Mango247, Stuffybear

Here is my solution which may be equivalent to the ones above (I haven't read the ones above yet.)

Case 1: There exists a 4-klique
Let the 4 klique be ABCD. Then clearly, every 3-klique must intersect ABCD in at least 2 points. Now suppose that there exist kliques WLOG EAB and FCD. If E and F are the same point, then EABCD is a 5-klique. if they are not the same point, then EAB and FCD are disjoint, thus this is impossible. Therefore, suppose point E exists such that EAB is a 3 klique. Then ever other 3 klique MUST contain either A or B. Thus deleting A and B suffices.

Case 2: THere is no 4-klique but there exists ABCD such that B and C are not connected, but all other pairs are (so two triangles sharing an edge)
In this case, let us consider any 3-klique not containing A or D. Then, it clearly must contain B and C in order for the given constraint to hold. However B is not connected to C, thus all 3-klique's contain either A or D. Thus, deleting the two of them suffice.

Case 3: All 3-klique's intersect at one point exactly.
Suppose we have kliques ABC and ADE. Now, in order for any other klique to intersect both of these kliques but not go through A, it must contain WLOG B and D. However B and D are not connected by the given above, thus we have a contradiction. Hence all 3-kliques go through A which means deleting A suffices.

Z K Y

The post below has been deleted. Click to close.

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

math154

4302 posts

math154

#8 h Jun 1, 2011, 1:25 AM • 4 Y

Y by JackXD, CaptainLevi16, Adventure10, Mango247

Suppose otherwise; let $f(X,Y)$ denote the assertion that there must exist a triangle not containing either of $X,Y$ and $g(UVW)$ for a triangle $UVW$ denote the assertion that each triangle in $G$ must contain at least one of $U,V,W$ .

Start with a triangle $ABC$ , so $f(B,C),g(ABC)$ force the existence of triangle $ADE$ with $\{D,E\}\cap\{B,C\}=\emptyset$ . Then from $f(A,C),g(ACB),g(ADE)$ , WLOG $BD$ is an edge, and from $f(A,B),g(ABC),g(ABD)$ , $CD$ must be an edge. Finally, $f(A,D),g(ADC),g(ADE),g(ADB)$ together imply that $CEB$ must be a triangle, so $ABCDE$ form a $K_5$ , which is impossible.

Z K Y

The post below has been deleted. Click to close.

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

AnonymousBunny

339 posts

AnonymousBunny

#9 h Aug 29, 2014, 7:28 PM • 1 Y

Y by Adventure10

Solution

Z K Y

The post below has been deleted. Click to close.

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

ABCDE

1963 posts

ABCDE

#10 h May 15, 2016, 7:20 PM • 1 Y

Y by Adventure10

If two triangles share exactly one vertex call that vertex a joint and if two triangles share an edge call the edge a hinge.

Take a triangle $abc$ . Since all triangles have at least one vertex in common, every triangle forms a hinge or a joint with $abc$ . If at most two of $a,b,c$ are joints, we can remove them (and possibly another one or two of $a,b,c$ and no triangle remains).

Suppose that all three of them are joints. Let $auv$ , $bwx$ , $cyz$ be the triangles that are jointed to $abc$ . We will split into cases depending on how $auv$ , $bwx$ , $cyz$ are connected.

Case 1: All three are connected by hinges.

Note that since the three triangles don't share any edges with $abc$ , the three triangles must all have a common hinge of $uv$ , $wx$ , $yz$ . This forms a $K_5$ with $abcuv$ , a contradiction.

We can't have exactly two of the pairs among $auv,bwx,cyz$ connected by a hinge because the hinge would have to be common.

Case 2: Two triangles are connected by hinges, and each are connected to the other triangle by a joint.

WLOG suppose that $u=w$ , $v=x$ . We can't have $\{y,z\}=\{u,v\}$ or they would all have a common hinge, so WLOG $y=u$ and $z\neq v$ . We now have the triangles $cuz$ and $avb$ that are disjoint, a contradiction.

Case 3: All three are connected by different joints.

This means that we must have something isomorphic to $u=z$ , $v=w$ , $x=y$ . But now $auv$ and $bxc$ are disjoint, a contradiction.

Case 4: All three are connected by a common joint.

Suppose that $u=w=y$ , and $v\neq x\neq z$ . Now, by considering the triangles $auv$ , $bux$ , $cuz$ , we have that any triangle that does not have $u$ as a vertex must be of the form $pqr$ , where $p\in\{a,v\}$ , $q\in\{b,x\}$ , $r\in\{c,z\}$ . We can't have $vxz$ since that would be disjoint from $abc$ . Now we have two distinct cases to take care of since everything is isomorphic to one of these. If it's $axz$ then it's disjoint from $buc$ , a contradiction. If it's $abz$ then $abcuz$ is a $K_5$ , a contradiction. Hence, there are no other triangles that don't have $u$ as a vertex and we can just remove $a$ and $u$ .

Z K Y

The post below has been deleted. Click to close.

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

FISHMJ25

293 posts

FISHMJ25

#11 h Jul 25, 2018, 5:06 PM • 1 Y

Y by Adventure10

First there is triangle ABC.Suppose claim is false.All triangles have at least one of points A,B, or C then if we remove some two of them there must exist another triangle containing third point.So there exist 3 triangles (number of triangles bigger than or equal to 4) such that they contain only one of A,B,C.Now analyze 2 cases how these triangles are connected (takes no more that 5 min) and we are done .

This post has been edited 1 time. Last edited by FISHMJ25, Jul 25, 2018, 5:07 PM

Z K Y

The post below has been deleted. Click to close.

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

qq1075608078

3 posts

qq1075608078

#12 h Aug 14, 2018, 1:40 PM • 2 Y

Y by Adventure10, Mango247

grobber wrote:

I'd love to see another solution..

It's clearly impossible to have more than two triangles s.t. each two have a common edge, so count this case out. Take two triangles $xyz,xuv$ s.t. $\{x,y\}\cap\{u,v\}=\emptyset$ . Assume first that all of our triangles which don't have $x$ as a vertex have their vertices among $y,z,u,v$ . There must be such a triangle which doesn't have $y$ as a vertex, and the same holds for $z,u,v$ , so $xyzuv$ is a $K_5$ , which can't be true. This means that among the triangles which don't have $x$ as a vertex, we can find one $tvz$ (for example) s.t. $t\notin\{x,y,z,u,v\}$ .

Assume now that the conclusion doesn't hold. This means that we can find triangles which don't have $(x,v),(v,x)$ or $(z,x)$ as vertices. After noticing that $yu,ut,ty$ can't be edges, we can see that the only way this can happen is to have another vertex $p$ and triangles $pxt,pyv,puz$ . This, however, means we have the $K_5$ $xyzvp$ , a contradiction.

why cannot have more than two triangles s.t. each two have a common edge,?? for example {abc ,abd,abe}
i also wonder if in this graph there are no triangles at all then every persons departure leaves no triangle, is it a contradiction?

This post has been edited 1 time. Last edited by qq1075608078, Aug 14, 2018, 1:42 PM
Reason: need help

Z K Y

The post below has been deleted. Click to close.

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

qq1075608078

3 posts

qq1075608078

#13 h Aug 14, 2018, 1:51 PM • 1 Y

Y by Adventure10

grobber wrote:

I'd love to see another solution..

It's clearly impossible to have more than two triangles s.t. each two have a common edge, so count this case out. Take two triangles $xyz,xuv$ s.t. $\{x,y\}\cap\{u,v\}=\emptyset$ . Assume first that all of our triangles which don't have $x$ as a vertex have their vertices among $y,z,u,v$ . There must be such a triangle which doesn't have $y$ as a vertex, and the same holds for $z,u,v$ , so $xyzuv$ is a $K_5$ , which can't be true. This means that among the triangles which don't have $x$ as a vertex, we can find one $tvz$ (for example) s.t. $t\notin\{x,y,z,u,v\}$ .

Assume now that the conclusion doesn't hold. This means that we can find triangles which don't have $(x,v),(v,x)$ or $(z,x)$ as vertices. After noticing that $yu,ut,ty$ can't be edges, we can see that the only way this can happen is to have another vertex $p$ and triangles $pxt,pyv,puz$ . This, however, means we have the $K_5$ $xyzvp$ , a contradiction.

i cant understand the meaning of this problem totally confused... if ther exists 2 triangles like{a,b,c}and {a,d,e}, then only deleting a can leave no triangles if exist 2 triangles like {abc}{abd} then only a,b satisfy the reqirement ...but what is the use of the 5 clique?

Z K Y

The post below has been deleted. Click to close.

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

yayups

1614 posts

yayups

#14 h Aug 30, 2018, 6:05 AM • 2 Y

Y by Adventure10, Mango247

qq1075608078 wrote:

grobber wrote:

I'd love to see another solution..

It's clearly impossible to have more than two triangles s.t. each two have a common edge, so count this case out. Take two triangles $xyz,xuv$ s.t. $\{x,y\}\cap\{u,v\}=\emptyset$ . Assume first that all of our triangles which don't have $x$ as a vertex have their vertices among $y,z,u,v$ . There must be such a triangle which doesn't have $y$ as a vertex, and the same holds for $z,u,v$ , so $xyzuv$ is a $K_5$ , which can't be true. This means that among the triangles which don't have $x$ as a vertex, we can find one $tvz$ (for example) s.t. $t\notin\{x,y,z,u,v\}$ .

Assume now that the conclusion doesn't hold. This means that we can find triangles which don't have $(x,v),(v,x)$ or $(z,x)$ as vertices. After noticing that $yu,ut,ty$ can't be edges, we can see that the only way this can happen is to have another vertex $p$ and triangles $pxt,pyv,puz$ . This, however, means we have the $K_5$ $xyzvp$ , a contradiction.

i cant understand the meaning of this problem totally confused... if ther exists 2 triangles like{a,b,c}and {a,d,e}, then only deleting a can leave no triangles if exist 2 triangles like {abc}{abd} then only a,b satisfy the reqirement ...but what is the use of the 5 clique?

Consider the case where there are 5 people who all know each other. Clearly all 3-cliques intersect. But if two people leave, there is still a 3-clique. So it is necessary to assume no 5 cliques

Z K Y

The post below has been deleted. Click to close.

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

yayups

1614 posts

yayups

#15 h Aug 30, 2018, 6:07 AM • 3 Y

Y by e_plus_pi, Adventure10, Mango247

Here is my solution.

Suppose $G$ is a graph with no $K_5$ such that every two triangles in $G$ share a vertex, but it requires at least three vertices to delete to get rid of all triangles. We will now derive a contradiction.

If every two triangles shared an edge, we could delete the two vertices of that edge to get rid of all triangles, so it must be the case that there is some triangle $abc$ and some triangle $axy$ (here all lettered vertices are assumed to be distinct). Since $abcxy$ can't be a $K_5$ , one of $bx,by,cx,cy$ is not an edge. WLOG, assume $bx$ is not an edge.

Claim: There exists a unique vertex $z$ such that $zby$ and $zcx$ are triangles.

Proof of Claim: Consider a triangle $\Delta$ that doesn't contain $a$ . It must have one of $b$ and $c$ , and one of $x$ and $y$ (it has to share a vertex with $abc$ and $axy$ ). Therefore, one of $cy,by,cx$ is an edge of $\Delta$ .

If there were no triangles that had $by$ as an edge, then we could simply delete $c$ and $a$ , and any such $\Delta$ would get destroyed, and any triangle that did happen to have $a$ would also get destroyed. Therefore, there is a triangle with $by$ as an edge. Similarly we see that there is a triangle with $cx$ as an edge. Now those two triangles must intersect at one vertex, call it $z$ .

We now show uniqueness of $z$ . Suppose $z'$ was a vertex such that $z'by$ and $z'cx$ were triangles. But then $z'by$ and $zcx$ would have no vertices in common, so $z'$ can't exist, as desired. Thus the claim is proven. $\blacksquare$

We now have triangles $zby,zcx,abc,axy,aby,acx$ . To prevent $abycz$ from becoming $K_5$ , we must have that $cy$ is not an edge. We claim that every other triangle must have either $z$ or $a$ . Suppose $\Delta$ didn't have $z$ or $a$ . Therefore, it must have one from each of the pairs $(b,c),(x,y),(b,y),(c,x)$ . Therefore, it must contain either $bx$ or $cy$ , a contradiction. Therefore, all triangles contain either $z$ or $a$ , so deleting $z$ and $a$ kills all triangles. But we had assumed that it takes at least three vertices deleted to accomplish such a feat, so we have arrived at the desired overall contradiction.

Z K Y

The post below has been deleted. Click to close.

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

csaltachin

75 posts

csaltachin

#16 h Oct 6, 2018, 2:14 PM • 2 Y

Y by Adventure10, Mango247

Naturally we’ll speak in graphs. Ignore any vertex that doesn’t lie in any triangle. Start with any triangle and label its vertices $A,B,C$ . Clearly any other triangle contains at least one of $A,B,C$ .

We denote a triangle (distinct of $ABC$ ) as:
- an $A’-$ triangle if it only intersects $ABC$ at $A$ , and a $B’-$ and $C’-$ triangle similarly.
- an $AB-$ triangle if it intersects $ABC$ at both $A,B$ , and similarly for $BC-$ and $AC-$ triangles.

If there were (wlog) no $C’-$ triangles, then all triangles contain $A$ and/or $B$ , so removing them we’re done. Now assume there is at least one $A’-$ , $B’-$ and $C’-$ triangle; let them be $ADX$ , $BEY$ , $CFZ$ .

We will prove the lemma: all triangles that intersect $ABC$ at only one vertex share a vertex $K$ themselves.
To prove this, we first prove any three of them concur. We consider two cases:

a) $D,E,F$ are not all the same vertex; wlog $D\neq E$ . In order for $ADX$ and $BEY$ to intersect we must have $X=Y$ . We notice that $ABX$ is a triangle. Now, assume neither of $F,Z$ is $X$ ; then since $CFZ$ is a $C’-$ triangle, and since clearly $C\neq Z$ , $CFZ$ does not intersect $ABX$ , absurd. Then we set $K=X$ .
b) $D=E=F$ . Then we set $K=D$ .

Notice that in both cases we have that $ABK$ , $BCK$ , $ACK$ are triangles. Assume wlog an $A’-$ triangle doesn’t contain $K$ . By definition it doesn’t contain $B$ or $C$ either, so it does not intersect triangle $BCK$ , a contradiction. Similarly for $B’-$ and $C’-$ triangles, we have proved the lemma.

We know focus on (wlog) $AB-$ triangles. Assume such a triangle distinct from $ABK$ exists: let it be $ABN$ . Take a $C’-$ triangle $CFK$ ; in order for them to intersect, we must have $N=F$ . Then $F$ is adyacent to $A,B,C,K$ , meaning $ABCKF$ is a 5-clique, a contradiction.

Similarly for $BC-$ and $AC-$ triangles, we conclude that all triangles other than $ABC$ , $ABK$ , $BCK$ , $ACK$ intersect $ABC$ at exactly one vertex, hence they contain $K$ . Thus, by removing $K$ the only triangle remaining is $ABC$ , and removing any of its vertices, we are done.

This post has been edited 1 time. Last edited by csaltachin, Oct 6, 2018, 2:34 PM

Z K Y

The post below has been deleted. Click to close.

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

aops29

452 posts

aops29

#17 h Dec 7, 2019, 1:25 PM • 5 Y

Y by AlastorMoody, MathBoy23, Purple_Planet, Adventure10, Mango247

Solution

Z K Y

The post below has been deleted. Click to close.

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

pad

1671 posts

pad

#18 h Aug 15, 2020, 10:03 PM • 1 Y

Y by Purple_Planet

Consider a graph with two people connected if they are acquainted. Suppose that it is not possible to delete two vertices and end with no triangles.

Claim: There cannot be any 4-cliques.
Proof: Suppose $abcd$ is a 4-clique for some vertices $a,b,c,d$ . If there are no other vertices, just delete $a,b$ . Else, suppose $x$ is a vertex, and suppose it creates a triangle, WLOG $\triangle bdx$ . Then $acx$ cannot be a triangle, since otherwise $abcdx$ would be a 5-clique. Hence, any new triangle must have one vertex be $b$ or $d$ , by considering $\triangle bdx$ . So deleting $b,d$ leaves us with no triangles, contradiction. $\blacksquare$

Claim: There cannot be 2 triangles with a common edge.
Proof: Suppose triangles $\triangle abx$ and $\triangle aby$ existed for some vertices $a,b,x,y$ . Note that $xy$ is not an edge, else $abxy$ would be a 4-clique. Now, any other triangle must have one vertex be $a$ or $b$ . So deleting $a,b$ leaves no triangles, contradiction. $\blacksquare$

Now, suppose $\triangle ax_1x_2$ and $\triangle ay_1y_2$ are triangles and share vertex $a$ . Consider the set $S=\{x_1y_1,x_1y_2,x_2y_1,x_2y_2\}$ of possible edges. Suppose one of these is an edge, WLOG $x_2y_2$ . Suppose $x_2y_2$ creates a triangle; $\triangle x_2y_2z$ , for some $z$ . If $z\in \{x_1,y_1\}$ , then we can delete $a,z$ to win. So $z\not\in \{x_1,y_1\}$ . But then $\triangle ax_2y_2$ and $\triangle x_2y_2z$ share an edge, contradiction. Therefore, none of $S$ is an edge. We are almost done; finally notice that there cannot be a new triangle $\triangle ax_3y_3$ , since any edge then would create two triangles sharing an edge. In conclusion, only $\triangle ax_1x_2$ and $\triangle ay_1y_2$ exist, and now we delete $a$ and win.

Remarks

Z K Y

The post below has been deleted. Click to close.

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

dchenmathcounts

2443 posts

dchenmathcounts

#19 h Sep 12, 2020, 8:47 PM

Y by

Done with eisirrational and Aryan-23.

My writeup

eisirrational's writeup

Z K Y

The post below has been deleted. Click to close.

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

SnowPanda

186 posts

SnowPanda

#20 h Jan 31, 2022, 12:42 AM

Y by

Solution

Z K Y

The post below has been deleted. Click to close.

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

awesomehuman

496 posts

awesomehuman

#21 h May 21, 2022, 2:07 AM

Y by

Assume towards a contradiction two or fewer people can't leave and leave no $3$ -clique remaining. Represent the people as vertices on a graph that are connected if the two people are acquainted.

Then, there must exist a $3$ -clique of vertices $A$ , $B$ , $C$ . Note that for each pair, there must be a $3$ -clique not including that pair. Applying this logic to $(A, B)$ , $(B, C)$ , and $(C, A)$ and because we find that each of $A$ , $B$ , and $C$ must be in a $3$ -clique without the other two. Each pair of these $3$ -cliques must share a vertex.

Assume towards a contradiction that they all share $2$ points. Then, the graph will have a $K_5$ , a contradiction. So, there's a pair of these $3$ cliques, one connected to $B$ and one connected to $C$ (wlog) that only share $1$ vertex. Let $X$ be the shared vertex, and let $B'$ and $C'$ be the non-shared vertex besides $B$ or $C$ in the $3$ -cliques connected to $B$ and $C$ , respectively. So, the graph looks like a Sierpinski triangle with 4 small triangles with $A$ , $B'$ and $C'$ being the main vertices.

We claim $A$ is connected to $X$ . There has to be a $3$ -clique not including $B$ and $C$ . Since it must share vertices with $ABC$ and $XBC$ and it doesn't have $B$ or $C$ , it must have $A$ and $X$ . By the same logic, $C'$ and $B$ are connected and $B'$ and $C$ are connected. Note $AC'$ , $AB'$ , and $B'C'$ cannot be edges since otherwise there would be a $K_5$ .

Therefore, the $3$ -clique without $B$ and $C$ (which includes $A$ and $X$ ) must include a vertex besides $A, B, C, B', X, C'$ . Call that $Y$ . By similar logic, the $3$ -clique with $B'C$ and the one with $C'B$ must also include a vertex besides $A, B, C, B', X, C'$ . Because the $3$ -cliques with $BC'$ and $CB'$ must share a vertex with $AXY$ , they must include $Y$ . However, this creates multiple $K_5$ 's, a contradiction.

Z K Y

The post below has been deleted. Click to close.

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

awesomeming327.

1687 posts

awesomeming327.

#22 h Jun 6, 2022, 3:52 AM

Y by

Denote the people by $A_1,A_2,\dots,A_n.$ If there is only one clique the problem is trivial.

Suppose there are two $3$ -cliques that share two people, say $A_1,A_2,A_3$ and $A_1,A_2,A_4.$ Now, removing $A_3,A_4$ would break every 3-clique unless there is 3-clique that contains neither $A_3$ nor $A_4.$ Then this clique must contain both $A_1$ and $A_2.$ Let this clique be $A_1,A_2,A_5.$ Now, we claim that removing $A_1,A_2$ does the job. If any 3-clique remains, it must contain $A_3,A_4$ and $A_5$ which creates a 5-clique, a contradiction.

If there are not two 3-cliques that share two people then let two $3$ -cliques be $A_1,A_2,A_3$ and $A_1,A_4,A_5.$ We claim: removing $A_1$ does the job. Otherwise, if a 3-clique still remains it must have $A_2$ or $A_3$ and it must have $A_4$ or $A_5.$ WLOG, let it have $A_2$ and $A_4$ which means $A_1,A_2,A_4$ is a 3-clique. However, that creates two 3-cliques that share two people, so we're done by the previous part.

Z K Y

The post below has been deleted. Click to close.

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

th1nq3r

146 posts

th1nq3r

#23 h Aug 25, 2022, 10:19 PM

Y by

A pleasure to solve for certain!

The intuition behind this is that if we consider $K_5$ and remove two people, we are left behind with a $3$ -clique. With this we may assume the contrary and derive a contradiction.

Assume $\exists$ two people when upon departing leaves behind a $3$ -clique. Let the members of this initial $3$ -clique be $A, B, C$ . If people $D, E$ arrive once more, we have the following subsequent $3$ -cliques: $ABD, ABE, ACD, ACE$ , all with a common member $A$ . Now we have that each person knows four other people. Hence we have a $5$ -clique, which is a contradiction.

If a single person say $E$ departs, we have that there is a $4$ -clique among the remaining $A, B, C, D$ . Hence upon $E$ rekindling himself with the party, we have the new set of $3$ -cliques $ABE, ACE, ADE$ , which then form a $5$ -clique. (In particular $4$ -cliques aren't permitted). $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

cj13609517288

1879 posts

cj13609517288

#24 h May 8, 2023, 5:48 PM

Y by

Consider an arbitrary triangle(the result is obvious if there are no triangles) $ABC$ in the graph. Then every other triangle must share at least one vertex with $ABC$ .

Claim. If there exists three triangles $T_1$ , $T_2$ , $T_3$ such that $T_1\cap ABC=A$ , $T_2\cap ABC=B$ , $T_3\cap ABC=C$ , then these three triangles share a common vertex.
Proof. Assume FTSOC that there does exist $T_1=P_1P_2A$ , $T_2=Q_1Q_2B$ , $T_3=R_1R_2C$ that don't have a common vertex. Then consider $T_1\cap T_2$ , $T_1\cap T_3$ , and $T_2\cap T_3$ .
Case 1. All three of these have two points. WLOG $P_1=Q_1=R_1$ and $P_2=Q_2=R_2$ , then $ABCP_1P_2$ is a $K_5$ , contradiction.
Case 2. Two of these have two points and the other has one. WLOG $Q_1=R_1$ , $Q_2=R_2$ , $P_1=Q_1$ , $P_2=Q_2$ . But then we necessarily have $P_1=R_1$ , $P_2=R_2$ , so $T_1\cap T_3$ also has two points, contradiction.
Case 3. One of these has two points and the other two have one point. WLOG $Q_1=R_1$ , $Q_2=R_2$ , and $P_1=Q_1$ . Then $P_1=R_1$ as well. But then $AP_1P_2$ and $BCR_2$ are two disjoint triangles, contradiction.
Case 4. All of these have one point. Then WLOG $P_1=Q_1$ .
Subcase 1. $Q_1=R_1$ . Then $P_1=R_1$ and we have a common vertex, contradiction.
Subcase 2. WLOG $Q_2=R_1$ . Then $R_2=P_2$ . But then $AP_1P_2$ and $BCQ_2$ are two disjoint triangles, contradiction.

So if no three of these triangles exist, we can just remove two vertices of $ABC$ and finish. Otherwise...

Claim. This common vertex is common to every triangle besides $ABC$ itself.
Proof. Call the triangle $T$ . If $T\cap ABC$ has one point, apply the previous claim to $T_1$ , $T_2$ , $T_C$ , for example. Otherwise, $T\cap ABC$ has two points, say $AB$ , so let $T=ABX$ . $T$ must intersect $CR_1R_2$ , so either $T=R_1$ or $T=R_2$ . The former is what we want, so assume FTSOC that $T=R_2$ . But then $ABCR_1R_2$ is a $K_5$ , contradiction.

Thus we can remove the common vertex and $A$ to finish. QED.

Z K Y

The post below has been deleted. Click to close.

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

vsamc

3787 posts

vsamc

#25 h Jun 29, 2023, 2:11 AM

Y by

Solution

Z K Y

The post below has been deleted. Click to close.

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

PEKKA

1835 posts

PEKKA

#26 h Aug 4, 2023, 6:59 PM

Y by

Does this sol work?
Claim: For any number of cliques at this party, the departure of two people results in no 3-cliques remaining.
We will solve this by induction.
Let the people at the party be vertices, and let there be an edge between two people if they are acquainted with each other.
Let $c$ denote the number of cliques.
Base Case: $c=1$
This is obviously true. The deletion of any vertex works.

Inductive step: Assume the property holds for $c=n$ . We will prove that it works for $c=n+1.$
We can add one more clique and abide by the conditions of the problem by adding in one or two points.

Case 1: We add 1 vertex. Call this vertex $P$ . Let $P$ be in a clique with vertices $R$ and $S$ . Note that $deg(P)=2$ . By the problem statement, every pair of 3-cliques has at least one person in common. This means that every 3 clique contains either $P,Q$ or $R.$ However, since $deg(P)=2,$ we can say that every 3 clique contains either $R$ or $S.$ so the deletion of those vertices result in no 3-cliques remaining.

Case 2: We add 2 vertices. Call them $A$ and $B.$ There exists a point that forms the 3-clique with $A$ and $B.$ Call it $C.$ Note that $deg(A)=deg(b)=2.$ By similar logic to case 1, every 3-clique contains $C$ , so the deletion of vertex C results in no 3-cliques remaining.
Therefore we have just proved $c=n$ implies $c=n+1$ so our induction is complete.

Therefore for any number of cliques, the departure of 2 or fewer people results in no 3-cliques remaining.

Z K Y

The post below has been deleted. Click to close.

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

shendrew7

793 posts

shendrew7

#27 h Jan 3, 2024, 5:25 PM • 1 Y

Y by SSaad

Case 1: The graph contains a $K_4$ .

Each additional triangle must share exactly two vertices with this $K_4$ . If 3 or fewer vertices are used by the subsequent triangles, we're finished with Pigeonhole. Otherwise, all subsequent triangles have one common vertex in this $K_4$ , from which we also conclude.

Case 2: The graph does not contain a $K_4$ , but at least one pair of triangles share an edge.

Each subsequent triangle must have one of its vertices on this edge to avoid forming a $K_4$ .

Case 3: The graph does not contain a $K_4$ , and no two triangles share an edge.

There must be exactly one vertex which lies on every triangle to avoid a contradiction. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

joshualiu315

2513 posts

joshualiu315

#28 h Feb 29, 2024, 2:06 AM

Y by

If there is only one triangle, we can remove any of its vertices and it will be gone.

Suppose there are two triangles $ABC$ and $ABD$ . Notice that if we remove $C$ and $D$ , any triangles remaining must contain $A$ and $B$ , say it is $ABE$ . Then, removing $A$ and $B$ would break any triangles since $CDE$ cannot exist (or else there is a $K_5$ ).

Suppose there are two triangles $ABC$ and $ADE$ . Notice that if $A$ were to be removed, a triangle similar to $ABD$ would need to exist, whence we are done by the previous part. $\square$

Z K Y

The post below has been deleted. Click to close.

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

asdf334

7586 posts

asdf334

#29 h May 13, 2024, 12:46 AM

Y by

review, will come back later to write up again

Assume for contradiction that for any two points there exists a triangle not containing them.

We have the following magical claim, which simplifies much of our work:
Claim: Given triangles $ABC$ and $ABD$ , the edge $CD$ must exist.
Proof: There must exist a triangle not containing $A$ or $B$ . Hence it contains $C$ and $D$ , so edge $CD$ exists.

Evidently a triangle $ABC$ exists. As there must exist a triangle not containing $B$ or $C$ which therefore contains $A$ , it follows that there exist two triangles $ABC$ and $ADE$ .

As there must exist a triangle not containing $A$ or $C$ it must contain $B$ and one of $D$ and $E$ . Hence assume WLOG $BD$ is an edge.

By the claim on $ADB$ and $ADE$ we know $BE$ is an edge.
By the claim on $ABC$ and $ABD$ we know $CD$ is an edge.
By the claim on $BDC$ and $BDE$ we know $CE$ is an edge.

Thus $ABCDE$ is a $K_5$ and we have a contradiction. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

isomoBela

1 post

isomoBela

#30 h May 21, 2024, 5:21 PM • 2 Y

Y by Marinchoo, Triangle_Center

All induced 3-cliques should have in common at least (but not necessarily) one vertex. We will choose arbitrarily one 3-clique that we will call the 'central triangle' for the sake of the proof. This means that all 3-cliques in the graph should be connected to the central triangle. There are two possibilities for connections between the triangles: having a vertex in common, and having a 'side' (two vertices) in common, the latter is more limiting. If there exists a K_4, it should be such that either: 1) the central triangle is an induced subgraph from the K_4, or 2) sharing 2 vertices with the central triangle.

If there is no 3-clique in the graph G, we can remove any two vertices and we would have the statement proved.
Assuming there is not a K_4 in the graph, we can analyze several cases:

a. The central triangle (ABC) if it shares only one vertex with a neighboring triangle (let us say B), we have the structure (ABC),(BXY), such a structure could be broken by removing B. The possibilities for additional from ABC and BXY are AXZ, AYZ, CYZ, CXZ; we can simultaneously have all of them by removing Z, given that Z is the same vertex; if Z_0 is representing just any vertex, we can have AXZ_0 and CXZ_0, removed by deleting X, and AYZ_0 and CYZ_0, by removing Y. We cannot have a combination of AXZ_0 and CYZ_0 as they do not share a vertex in this case, as well as AYZ_0 and CXZ_0 due to the same reason.

b. The central triangle (ABC) is sharing a side with a neighboring triangle (BCZ), in this case, to remove all 3-cliques we remove one of the shared vertices. Additionally, infinitely many triangles can exist with new points based on both B and C (in such case, we again remove one of the shared vertices), or we can have additional structures based only on one of B/C. In this case, we can have ABC, BCZ, and the new one BXY. Since all of the triangles are laying on B, as a common point, any combination between the vertices is possible, but no growth of the structure unless it lays on B. So removing the point of the highest degree (B and C, as it is allowed) should resolve the issue.

Assuming there is a K_4 in the graph G, we want to show that we can remove any two of its vertices(the ones that are in the central triangle):

a.3-clique sharing a side with K_4 (ABCD) and central triangles (ABE): there cannot be a triangle with vertices incl. E except for variations of 3-cliques between the nodes: A, B, C, D; because EXY cannot be connected to triangles of type ABC). If we have a triangle DEC we would not be able to remove only two vertices (but as ABCDE is a K_5 it is forbidden), so we cannot have a triangle of that type, this is analogical for all cases. Any additional structure should rely on the cases with only 3-cliques, so removing two common vertices between the central triangle and the K_4 should suffice, which two depend on the other vertices.

b. Induced 3-clique ABC from K_4 (ABCD): No additional triangles can exist with less than 2 shared vertices with K_4. There can be build-up structures by using any two vertices, and in all cases, we can remove two vertices from the K_4 that are bases for distinct triangles with different vertices from the K_4 (allowed combinations are AB and DC, removing A and B; or AB, and CB, removing B and D (as D participated in ACD).

This post has been edited 1 time. Last edited by isomoBela, May 21, 2024, 5:24 PM

Z K Y

The post below has been deleted. Click to close.

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

Marinchoo

407 posts

Marinchoo

#31 h May 21, 2024, 5:25 PM • 1 Y

Y by isomoBela

If there is a $K_4$ with vertices $A$ , $B$ , $C$ , and $D$ , then any triangle outside it must have a common side with this clique. Assume there is a $\triangle ABE$ , and note that we can remove vertices $A$ and $B$ in this case. If a triangle remains, it must be $CDE$ , as $ABC$ , $ABD$ , and $ABE$ are triangles in $G$ . However, if $CDE$ is also a triangle, then $ABCDE$ is a $K_5$ , contradiction. If there are no triangles outside the $K_4$ , we're also trivially done by removing $A$ and $B$ . If there's no $K_4$ in the graph, assume two triangles share a side (let them be $ABC$ and $BCD$ ). Then, we can remove $B$ and $C$ , and if a triangle can still be found, it must have $A$ and $D$ as vertices, but $AD$ is not an edge as $ABCD$ can't be a $K_4$ , contradiction. Hence, we're left with the case when two triangles share exactly one vertex. Say two of these are $ABC$ and $BXY$ . We commit to removing $B$ . Assume that some triangles are left (at least one). Then they must be of the form $AXZ$ , $AYZ$ , $CYZ$ , or $CXZ$ for some $Z$ possibly among $A, C, X, Y$ . We'll consider two cases. Firstly, if at most one from both pairs of types of triangles $(AXZ, CYZ)$ and $(AYZ, CXZ)$ exists, notice that all remaining triangles include one of the vertices $A, C, X$ or $Y$ . If not, WLOG assume that there are triangles $AXZ$ and $CYZ_1$ . Then $Z=Z_1$ due to the problem condition. We now also remove $Z$ . Assume there are any triangles left. As this triangle must have a common vertex with every side of the cycle, $AXYC$ , $AY$ , or $CX$ must be a side in the triangle. In the former case, $ZCXY$ is a $K_4$ ; in the latter, $ZCAY$ is a $K_4$ contradiction.

Z K Y

The post below has been deleted. Click to close.

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

legogubbe

18 posts

legogubbe

#32 h Jul 28, 2024, 6:49 PM

Y by

Among the people, there is one, call him Bob, who is contained in the maximum number of $3$ -cliques. Remove Bob. If no $3$ -cliques remain, we are done. Otherwise, suppose that there still exists some $3$ -cliques after the departure.

Claim 1. After the departure there are no $4$ -cliques.
Proof. Suppose for the sake of contradiction one exists. Every member of this $4$ -clique is a member of at least three $3$ -cliques. But Bob and one of the members in the $4$ -cliques must have been members of the same $3$ -cliques, different from the $3$ -cliques in the $4$ -cliques. Thus, before the departure, one of the members in the $4$ -cliques must have been a member of at least four $3$ -cliques. By maximality, Bob must also have been a member of at least four $3$ -cliques. It should be clear that the other two members of each $3$ -clique Bob is contained in, must be members of the $4$ -clique. This means that Bob before the departure must have been acquainted with every member of the $4$ -clique, which is a $5$ -clique, which is not allowed. Contradiction. This contradiction proves our claim.

Claim 2. After the departure, one is a member of each remaining $3$ -cliques.
Proof. Suppose for the sake of contradiction the claim is false. Then there exist six people $\mathsf{A}$ , $\mathsf{B}$ , $\mathsf{C}$ , $\mathsf{a}$ , $\mathsf{b}$ and $\mathsf{c}$ such that $\{\mathsf{A},\mathsf{b},\mathsf{c}\}$ , $\{\mathsf{B},\mathsf{c},\mathsf{a}\}$ and $\{\mathsf{C},\mathsf{a},\mathsf{b}\}$ are all $3$ -cliques. Note $\{\mathsf{a},\mathsf{b},\mathsf{c}\}$ also is a $3$ -clique. It should be clear that the other two in every $3$ -cliques that Bob was contained in must be two of $\mathsf{A}$ , $\mathsf{B}$ , $\mathsf{C}$ , $\mathsf{a}$ , $\mathsf{b}$ or $\mathsf{c}$ . Bob could not be acquainted with any of $\mathsf{A}$ , $\mathsf{B}$ or $\mathsf{C}$ , because if he was, then either one of the pairs $\{\mathsf{A},\mathsf{a}\}$ , $\{\mathsf{B},\mathsf{b}\}$ or $\{\mathsf{C},\mathsf{c}\}$ are acquainted, which creates a $4$ -clique after the departure, contradicting the first claim of ours, or, there would be two disjoint $3$ -cliques, which also is not allowed. Hence, Bob must have been acquainted only with some of $\mathsf{a}$ , $\mathsf{b}$ or $\mathsf{c}$ . Since each of $\mathsf{a}$ , $\mathsf{b}$ and $\mathsf{c}$ are members of at least three $3$ -cliques after the departure it follows that one of them before the departure were members of at least four $3$ -cliques. But, there are at most three $3$ -cliques Bob could have been in among $\mathsf{a}$ , $\mathsf{b}$ and $\mathsf{c}$ , contradicting maximality. This contradiction proves our claim.

The problem follows immediately from our second claim. We are done!

Z K Y

The post below has been deleted. Click to close.

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

Markas

105 posts

Markas

#33 h Oct 4, 2024, 6:31 PM

Y by

First, we will check the case where there is a $K_4$ . Let it have vertices A, B, C, and D. Now any triangle outside the $K_4$ must have a common side with it. Assume there is a $\triangle ABX$ , and we can remove A and B and we are okay. If there is a $\triangle$ still, it must be $\triangle CDX$ , since the other triangles have A or B as a vertex. Now if $\triangle CDX$ exists, it follows that ABCDX is a $K_5$ - contradiction. If there aren't any triangles outside the $K_4$ , we just have to remove A and B and we would be ready. Now let the graph have no $K_4$ 's in it. Now assume there are two triangles that have a common edge and let them be $\triangle ABC$ and $\triangle BCD$ . Now if we remove B and C, there should be no triangle left except if it has A and D as vertices, but if A and D are vertices in a triangle, the edge AD should exist, but if it does we have that ABCD is a $K_4$ - contradiction. Now we are only left to check the case when two triangles share exactly one vertex. Let two triangles with only one common vertex be $\triangle ABC$ and $\triangle BMN$ and we obviously want to remove B. Now assume that there still exist some triangles after removing B. Then they must be some of $\triangle AMP$ , $\triangle ANP$ , $\triangle CNP$ , or $\triangle CMP$ for a vertex P. Now if at most one from the pairs of $\triangle (AMP, CNP)$ and $\triangle (ANP, CMP)$ exists, we have that all remaining triangles have one of A, C, N, M as their vertex. If not, WLOG assume that there still exist $\triangle ANP$ and $\triangle CMP'$ and it is obvious that $P \equiv P'$ . If not, $\triangle ANP$ and $\triangle CMP'$ don't have a common vertex - contradiction. Now we should remove P too. Now we want to show that there are no triangles left and we will be ready. FTSOC assume there are still triangles left. Such triangle should have a common vertex with every side of the cycle AMNC, where AM or CN should be one of the triangle sides. In either scenarios, PCNM or PCAN are $K_4$ - contradiction $\Rightarrow$ there are no triangles left and we are ready.

Z K Y

The post below has been deleted. Click to close.

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

asdf334

7586 posts

asdf334

#34 h Mar 3, 2025, 2:54 AM

Y by

We use proof by contradiction; let $P(a,b)$ be the assertion that there exists a 3-clique not using $a$ or $b$ . Define $P(a)$ similarly.

Consider a 3-clique $(a,b,c)$ . From $P(b,c)$ we can define a second 3-clique $(a,d,e)$ , as the 3-clique must include $a$ .

Now from $P(a)$ there exists a 3-clique using one of $b$ or $c$ and one of $d$ or $e$ . WLOG assume the edge $cd$ exists.

Claim: If a 4-clique $(a,b,c,d)$ is missing all but one edge (WLOG $bc$ ), then the edge $bc$ exists too.
Proof: From $P(a,d)$ and the 3-cliques $(a,b,d)$ and $(a,c,d)$ we find there exists a 3-clique using $b$ and $c$ . $\square$

Now apply the claim on $(a,c,d,e)$ , $(a,b,c,d)$ , and finally $(b,c,d,e)$ to obtain that $(a,b,c,d,e)$ is a 5-clique, a contradiction. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

Marcus_Zhang

965 posts

Marcus_Zhang

#35 h Mar 30, 2025, 3:38 PM

Y by

First consider the case where we have a $K_4$ in the graph with the four vertexes $a,b,c,d$ . Now add in one more triangle: It must pass through two of $a,b,c,d$ so let's assume WLOG it's $eab$ .

$\textbf{Claim:}$ If we add any other triangle, it must pass through $a$ or $b$ .

$\textbf{Proof:}$ First assume the triangle doesn't pass through any of those points. Then we must have the triangle be $ecd$ , and this creates a $K_5$ so it's invalid.

Now, just remove $a,b$ and all triangles are removed.

Next, consider the absence of a $K_4$ . Then we break this up into cases. First, assume two triangles intersect at an edge (let the configuration be $abc$ , $dbc$ ). Then we can't have any triangle going through $ad$ because that creates a $K_4$ , contrary to our claim. All other triangles must pass through $b$ or $c$ , which finishes this case because we can just take $b,c$ to be removed.

If we don't have any triangles intersect at an edge, then we have at least two triangles intersect at only one vertex. Let these be $abc$ , $ade$ . We can't have a triangle include one of $b,c$ and one of $d,e$ because this violates the claim that no two triangles share an edge. Thus, we must have all triangles intersect at $a$ , so removing this vertex finishes the case.

Therefore, it is always possible to delete two vertexes from $G$ and obtain a graph with no triangles.

Z K Y