6.11

[Altheman]

is a finite graph such that it does not contain a
complete subgraph with 5 vertices, and any two triangles have
at least point in common. Show that there are at most two
points where removal leaves no triangles.

[bpgbcg]

Click to reveal hidden content

If there are no triangles, it is trivial. Assume there is at least one triangle. Each other triangle shares a vertex with that triangle. Assume for the sake of contradiction that there do not exist 2 such points. Then for each vertex of that triangle, there is another triangle that contains that vertex and no other vertices of the original triangle.
Lemma: There exists a complete 4-point subgraph of the graph.
By the above observation, no triangle we are considering shares 2 vertices with the original triangle. Then each of the three triangles at the corners must share a vertex with each other. If all three triangles share 1 vertex, there is clearly a complete 4-point subgraph (the original triangle and that vertex). If some two triangles share 2 vertices, there is again a complete 4-point subgraph. The last case is that there are 3 other points, each shared by 2 of the triangles

We can see that there are 2 triangles that do not share a common vertex, so the lemma is proven.
No triangle can share 0 or 1 vertices with this subgraph. Thus each triangle must share at least 2 points with it. The removal of any 2 points out of the 4 will remove all of the triangles among the 4 points of the subgraph, so we must just consider triangles sharing exactly 2 points with the subgraph. If we remove two of the points of the 4-point subgraph, and not all of the triangles are removed, there must be a triangle that contains the 2 other vertices of the 4-point subgraph, and is not fully contained in this subgraph. If we remove the other two vertices of the subgraph, there exists such a triangle which contains the other two points of the subgraph. These two triangles must share as vertex. The 4-point subgraph and this point together make up a complete 5-point graph, a contradiction.