1
$\begingroup$

I ran into the following problem when revising for a Graph Theory exam - I had already solved part c) however I am keeping it in as it seems to link to part d). Problem in question Now I see these type of problems on Turan graphs quite frequently, however, I have always struggled with problems such as these where it involves graphs with more edges than its Turan number.

The Turan number $t_r(n)$ represents the maximum number of edges a graph with $n$ vertices can have and not contain a copy of $K_{r+1}$. So in this case having $t_2(n) + 2$ edges would then contain at least a triangle. However, I am not sure how this would link together with subgraphs of size 5 or 7 - perhaps 5/7 vertices come from removing a vertex from a graph described in the previous part?

I'd be grateful if anyone could give any pointers on the general techniques / things to try when facing these problems.

$\endgroup$
3
  • $\begingroup$ $T_2$ is undefined. $\endgroup$
    – user21820
    Apr 14, 2022 at 9:57
  • $\begingroup$ @user21820 Thanks for the comment. $T_r(n)$ is the graph in en.wikipedia.org/wiki/Tur%C3%A1n%27s_theorem - the graph with $n$ vertices, and has the most edges among all graphs which do not contain a copy of $K_{r+1}$ $\endgroup$
    – CowNorris
    Apr 29, 2022 at 7:45
  • $\begingroup$ You should define all needed terms in your question (not in comments). After you edit your question, you can delete your comment and ping me to let me know so I can delete mine too. $\endgroup$
    – user21820
    Apr 29, 2022 at 7:58

1 Answer 1

1
$\begingroup$

A partial answer:

We use a similar proof structure here akin to the induction proof of Turan's theorem. We use induction on $|G|$, the number of vertices.

Base case, $n=5:$ Suppose $e(G) = t_2(5) + 2 = 8$. We just take subgraph $H \leq G$ with $H = G$ so $|H| = 5, e(H) = e(G) = t_2(5) + 2$

Inductive case: suppose true up to $|G| < n$, then for $|G| = n$:

Claim: $G$ has a subgraph $K'$ such that $\delta(K') \leq \delta(T_2(n))$, i.e. the min. degree of $K'$ is smaller than the min. degree of $T_2(n)$.

Proof of claim: Taking contrapositive of the last part of part c), we have that if $e(K') \leq t_2(n) + 2$ then $\delta(K') \leq \delta(T_2(n))$. Since $e(G) \geq t_2(n)+2$ it does indeed has a subgraph $K'$ with $e(K') = t_2(n) + 2$. So the lemma applies and $\delta(K') \leq \delta(T_2(n))$ as required.

By the claim, then, $K'$ has a vertex $v$ with $d(v) = \delta(K') \leq \delta(T_2(n))$. For $K = K'-v$ we have that $K \leq K' \leq G$, so $K$ is a subgraph of $G$ and:

$e(K) = e(K') - d(v) \geq (t_2(n) + 2) - \delta(T_2(n)) = t_2(n-1) + 2$ (last step by property of Turan graphs: $t_r(n) - \delta(T_r(n) = t_r(n-1)$).

Here the $IH$ applies on $K$ and $K$ has a subgraph $H$ with our desired properties, thus $H \leq K \leq G$ and $H$ is also a subgraph of $G$. As required.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .