\chapter{ $-G $ترید‌ها } \section*{ مقدمه } در این فصل هدف یافتن طیف $-G$ ترید برای چند خانواده از گراف‌ها است. فرض کنید گراف $G$ داده‌شده‌است، یک $T_G(s,v)$ یا به اختصار $T(s,v)$ یعنی، یک $-G$ ترید از حجم $s$ و اندازه بنیان $v$ وجود دارد؛ و یک $T_G(s;H)$ یعنی یک $-G$ ترید از حجم $s$ روی گراف اساسی $H$ وجود دارد. در این فصل ابتدا گراف‌های کامل چند بخشی را بررسی می‌کنیم که از \cite{parti Bil} و \cite{parti jame} استفاده شده‌است برای این منظور طیف ترید را با فرض نامحدود بودن اندازه بنیان، مانند نتایجی که در \cite{TG} بدست آمده، بررسی می‌کنیم. برای سایر گراف‌ها در این بخش طیف حجم ترید را برای هر اندازه بنیان $v$ ممکن بدست می‌آوریم. که این گراف‌ها ، $K_4-e,C_6,C_4,C_3$ ، ستاره و $C_5$ هستند که به ترتیب از \cite{star,K4-e,C6,C4,C3} و \cite{C5} استفاده شده‌است. \section{طیف ترید از گراف‌های چند بخشی کامل } \begin{definition} فرض کنید $n,a_1,a_2,\ldots, a_n$ اعداد صحیح مثبت هستند، گراف $-n$ بخشی کامل\\ $G=K(a_1,a_2,\ldots,a_n)$ ، را به شرح زیر تعریف می‌کنیم. رأس‌های $G$ به مجموعه‌های $A_i (1\leq i \leq n)$ ، به‌نام بخش‌های $G$ افراز می‌شود، که $\vert A_i \vert=a_i$ $(1 \leq i \leq n)$ ، است. دو رأس در $G$ مجاورند اگر و فقط اگر در دو بخش‌ متفاوت واقع باشند. اگر برای هر $i$ $(1 \leq i \leq n)$ ، $a_i=a$ باشد، به جای $K(a,a, \ldots ,a)$ از نماد $K_{n(a)}$ استفاده می‌کنیم. اگر $n=2 , 3$ باشد، معمولاً به ترتیب از نمادهای $K_{a_1,a_2}$ و $K_{a_1,a_2,a_3}$ استفاده می‌کنیم. \end{definition} اگر تمام بخش‌ها اندازه یک داشته‌باشند، آنگاه $G$ یک گراف کامل $K_n$ است. نتیجه زیر را برای کامل بودن بحث از \cite{kho} بازگو می‌کنیم: \begin{theorem}\label{1.1.1} $X(K_n)=\lbrace s \vert\; 1 \leq s \leq 2n-3 \rbrace \cup \lbrace s \vert \;2n-1 \leq s \leq 3n-4 , \text{فرد} \;s \rbrace $ ، با دقیقاً این استثنا‌ها: $TS(K_2)=\lbrace 0 \rbrace$ و $15 \in TS(K_7)$. \end{theorem} \begin{point} توجه کنید که طبق لم \ref{tg2.2} اگر $G$ گراف دوبخشی باشد، آنگاه $X(G) \subset \lbrace 1 \rbrace$ است. \end{point} \begin{definition} گوییم ترید $\{T_1,T_2\}$ زنجیری است، اگر $T_1= \lbrace G_i \vert\; 1\leq i \leq s \rbrace$ و \\ $T_2 = \lbrace G'_i \vert\; 1 \leq i \leq s \rbrace$ باشد، به‌طوری‌که برای هر $(1 \leq i \leq s)$ ، $V(G_i)=V(G'_i)$ باشد. \end{definition} بررسی طیف ترید برای گراف‌های چندبخشی کامل را به دو قسمت تقسم می‌کنیم:\\ 1) وقتی‌که بخش‌ها از اندازه‌های متفاوت هستند.\\ 2)وقتی‌که بخش‌ها اندازه یکسان دارند.\\ \subsection{ وقتی که بخش‌ها از اندازه‌های متفاوت هستند } \begin{lemma}\label{1.2.1} یک $-K_{1,2}$ ترید زنجیری از حجم $s$ برای $s \geq 3$ وجود دارد. \end{lemma} \begin{proof} فرض کنید گراف اساسی $H$ ، یک چرخ $W_s$ باشد، یعنی گرافی با مجموعه رأس‌ $\lbrace 1,2,\ldots, s ,\infty \rbrace$ و مجموعه یال $\lbrace ( \infty ,i) \vert\; 1 \leq i \leq s \rbrace \cup \lbrace (i,i+1) \vert\; 1 \leq i \leq s \rbrace (\textsc{ mod} \; s)$ است. آنگاه یک $-K_{1,2}$ ترید از حجم $s$ به وسیله $T_1=\lbrace G_1,G_2, \ldots , G_s\rbrace$ با زوج $T_2=\lbrace G'_1,G'_2, \ldots , G'_s\rbrace$ وجود دارد، که $V(G_i) = V(G'_i)=\lbrace 1,2,\ldots, s ,\infty \rbrace$ است و مجموعه یال هر $G_i$ $(1 \leq i \leq s)$ ، برابر است با، $\lbrace (\infty ,i) , (i,i+1) \rbrace (\textsc{mod}\; s)$ و مجموعه یال هر $G'_i$ $(1 \leq i \leq s)$ ، برابر است با، $ \lbrace (\infty ,i+1) , (i,i+1) \rbrace (\textsc{mod}\; s)$. \end{proof} نتیجه بالا از $K_{1,2}$ به گراف $K_{a,b}$ برای $(a < b)$ تعمیم داده‌می‌شود. به این صورت که در گراف $H$ در لم \ref{1.2.1} رأس $\infty$ را به $b-a$ رأس منفجر می‌کنیم(یعنی به‌جای رأس $\infty$ ، $b-a$ رأس جدید قرار می‌دهیم و به‌جای هر یال $(\infty,i)$ ، $b-a$ یال $(-,i)$ منتاظر با هر رأس جدید قرار می‌دهیم)، و هر رأس $i $ $ (1 \leq i \leq s)$ ، را به $a$ رأس منفجر می‌کنیم. \begin{lemma}\label{1.2.2} یک $-K_{a,b}$ ترید زنجیری $(a < b)$ ، از حجم $ s $ برای $ s \geq 3$ وجود دارد. \end{lemma} \begin{proof} فرض کنید $ H$ گرافی با مجموعه رأس $V_\infty \cup V_i $ $(1 \leq i \leq s )$ باشد، که $\vert V_\infty \vert= b-a , \vert V_i \vert = a $ است، و با مجموعه یال تمام یال‌های بین $V_\infty $ و $V_i $ $ (1 \leq i \leq s )$ ، به همراه با تمام یال‌های بین $V_i$ و $V_{i+1}$ $( 1 \leq i \leq s)$ ، است( به پیمانه $s$ ، پس وقتی $i=s $ باشد، $ i+1=1 $ است). آنگاه یک $-K_{a,b}$ ترید از حجم $s$ به وسیله $T_1=\lbrace G_1 ,\ldots , G_s \rbrace$ با زوج $T_2=\lbrace G'_1 ,\ldots , G'_s \rbrace$ داده می‌شود، که $V(G_i) = V(G'_i)=V_\infty \cup V_i \cup V_{i+1} $ و $ E(G_i)$ شامل تمام یال‌ها از $V_{\infty}$ به $V_i$ و از $V_i$ به $V_{i+1}$ است، در حالی‌که $E(G')$ شامل تمام یال‌ها از $V_{\infty}$ به $V_{i+1}$ و از $V_i$ به $V_{i+1}$ است. \end{proof} \begin{theorem}\label{1.2.3} فرض کنید $G$ گراف چند بخشی کامل $ K(a_1,a_2, \ldots , a_n)$ با $(a_1 < a_2)$ است. یک $-G$ ترید زنجیری از حجم $ s $ برای تمام $ s \geq 3 $ وجود دارد. \end{theorem} \begin{proof} لم \ref{1.2.2} ، برای $K_{a_1,a_2}$ را با استفاده از توسعه‌ی $H$ به صورت گفته‌شده بکار می‌بریم، و $ G_i $ را دارای مجموعه رأس $ V_\infty \cup V_i \cup V_{i+1} \cup X_i $ که ، $ \vert V_{\infty} \vert= a_2 - a_1 $ ، $ \vert V_i \vert= \vert V_{i+1} \vert =a_1 $ ، $ \vert X_i \vert= \sum_{j=3}^n a_j$ ، و $ G'_i$ را نیز دارای مجموعه رأس مشابه، در نظرمی‌گیریم. یال‌های $ G_i$ مانند لم \ref{1.2.2} هستند، به همراه یال‌های متناظر بین رأس‌های $X_i$ و یال‌هایی از $ X_i$ به $V_{\infty} , V_i$ و $V_{i+1}$ . به علاوه، یال‌های $G'_i$ مانند لم \ref{1.2.2} هستند، به همراه یال‌های اضافی مشابهی که برای $G_i$ شرح داده شد. \end{proof} در این‌جا شرط لازم و کافی برای وجود ترید‌ها از حجم $2$ را بیان می‌کنیم که اثبات آن در \cite{parti Bil} آمده‌است. \begin{theorem}\label{1.5.1} فرض کنید $ G $ گراف چندبخشی کامل است. آنگاه $ 2 \in TS(G) $ است، اگر و فقط اگر $G$ به صورت یکی از موارد زیر باشد:\\ (1) $ G $ یک یا دو بخش دارد، و $G \neq K_2 $.\\ (2) $ G=K(a_1,a_2,\ldots , a_p,a_{p+1}) $ ، که $ p \geq 2 $ و $ a_{p+1} = a_1 + (a_1 +a_2 + \ldots +a_p) $.\\ \end{theorem} \subsection{وقتی که بخش‌ها اندازه یکسان دارند} در این قسمت ابتدا نشان می‌دهیم که برای گراف $K_{n(p)}$ ، $(p \geq 2)$ هیچ تریدی از حجم $s$ ، $(s \leq min(n,5))$ وجود ندارد. \subsubsection{عدم وجود از حجم $s$، $ s \leq min(n,5) $} با دو خاصیت ساده از گراف‌های چند بخشی این بخش را شروع می‌کنیم. \begin{lemma}\label{2.2.1} (1) یک زیرگراف القایی از یک گراف چند بخشی کامل یک گراف چند بخشی است.\\ (2) اگر دو گراف چند بخشی کامل دقیقاً رأس‌های یکسان داشته‌باشند، و هر دو حداقل دو بخش داشته‌باشند، آنگاه باید حداقل یک یال مشترک داشته‌باشند. \end{lemma} \begin{proof} (1) درستی این موضوع فوراً از تعریف گراف چند بخشی کامل بدست می‌آید.\\ (2) فرض کنید $A$ و $B$ گراف‌های چند بخشی کامل روی مجموعه رأس یکسان باشند، که هر دو حداقل دو بخش دارند. فرض کنید $\overline{A}$ مکمل $A$ باشد. مکمل یک گراف $-n$ بخشی کامل اجتماعی از $n$ گراف کامل است. چون $A$ حداقل دو بخش دارد نتیجه می‌شود که $\overline{A}$ همبند نیست. اما $B$ همبند است، چون یک گراف چند بخشی کامل با حداقل دو بخش است. بنابراین $B$ نمی‌تواند زیرگرافی از $\overline{A}$ باشد. نتیجه می‌شود که $A$ و $B$ حداقل یک یال مشترک دارند. \end{proof} \begin{lemma}\label{2.2.2} فرض کنید $\lbrace T_1,T_2 \rbrace$ ، که $T_1 = \lbrace G_1,G_2,\ldots, G_s \rbrace$ و $T_2 = \lbrace G'_1,G'_2,\ldots, G'_s \rbrace$ ، یک اشتاینر ترید از حجم $s$ با بلوک‌های $G_i , G'_i \cong K_{n(p)}$ باشد. آنگاه برای $C = V(G_i) \cap V(G_j)$ ، $(1\leq i < j \leq s)$ داریم:\\ $(i)$ $C$ یک زیر مجموعه از یک بخش $V(G_i)$ است، یا $C$ یک زیر مجموعه از یک بخش $V(G_j)$ است، یا هر دو است؛\\ $(ii)$ $\vert C\vert \leq p$. به عبارت دیگر، حداقل یکی از $G_i \langle C \rangle$ یا $G_j \langle C \rangle$ (زیر گراف‌های القایی) هیچ یالی ندارند. \end{lemma} \begin{proof} طبق قسمت (1) لم \ref{2.2.1} ، هردوی $G_i \langle C \rangle$ و $G_j \langle C \rangle$ گراف چند بخشی کامل هستند. اگر هر دوی آن‌ها حداقل دو بخش داشته ‌باشند آنگاه طبق قسمت دوم لم \ref{2.2.1} باید حداقل یک یال مشترک داشته ‌باشند، که با تعریف یک اشتاینر ترید تناقض دارد. بنابراین حداقل یکی از این زیرگراف‌ها فقط یک بخش دارد. نتیجه می‌شود که $C$ یک زیر مجموعه از بلوک متناظر است( یعنی، اگر $G_i \langle C \rangle$ فقط یک بخش داشته باشد که دراین‌صورت هیچ یالی ندارد، آنگاه $C$ یک زیر مجموعه از یک بخش $V(G_i)$ است).\\ (2) فوراً از قسمت (1) نتیجه می‌شود. \end{proof} نتیجه اصلی این بخش اثبات این موضوع است که برای گراف $ K_{n(p)}$ ، $(n \geq 3)$ هیچ $- K_{n(p)}$ تریدی از حجم $s$ ، برای $ s\leq min(n, 5 )$ وجود ندارد. این را در دو قسمت نشان می‌دهیم: ابتدا نشان می‌دهیم، به شرط اینکه $ n\leq3 $ باشد، هر $- K_{n(p)}$ تریدی با $ s\leq n $ باید زنجیری باشد؛ سپس نشان می‌دهیم که هیچ $-K_{n(p)} $ ترید زنجیری از حجم کوچک‌تر یا مساوی پنج وجود ندارد. بنابراین عدم وجود برای تمام حجم ترید‌هایی که هر توسط دو لم پوشیده ‌می‌شوند، را ثابت می‌کنیم. قبل از شروع قسمت اول این استدلال، یک خاصیت از تمام $-G$ ترید‌های $ \lbrace T_1,T_2 \rbrace $ برای گراف‌های $-d$ منتظم را بیان می‌کنیم(مانند گراف‌های چندبخشی کامل که همه بخش‌ها اندازه یکسان دارند). اگر یک رأس $ v $ در $ n $ بلوک از $ T_1 $ واقع شود، آنگاه آن در گراف اساسی $ H $ درجه‌ی $nd$ دارد و بنابراین دقیقاً در $ n $ بلوک از $ T_2 $ واقع می‌شود. می‌گوییم $ n $ تعداد تکرار از $ v $ است،که در هر نیمه از ترید، $ T_1 $ و $ T_2 $ مساوی است. \begin{theorem}\label{22.2.1} فرض کنید گراف $G= K_{n(p)}$ ، $(n \geq 3)$ داده شده‌است، هر $-G$ ترید از حجم $s $ ، $(s \leq n)$ باید زنجیری باشد. \end{theorem} \begin{proof} یک بلوک از $T_1$ ، مثلاً $G_1$ را درنظربگیرید. طبق قسمت دوم لم \ref{2.2.2} ، حداکثر $p$ رأس $G_1$ در $G_i$ ، $(2 \leq i \leq s)$ نیز واقع است. بنابراین حداکثر $(s-1)p$ رأس از $G_1$ در یک بلوک یا بیشتر از یک بلوک دیگر از $T_1$ واقع می‌شود. چون $G_1$ ، $np$ رأس دارد و $s \leq n$ است، نتیجه می‌شود که $G_1$ حداقل $p$ رأس دارد که در هیچ بلوکی از $T_1$ واقع نمی‌شود. این رأس‌ها تعداد تکرار $1$ دارند، و بنابراین هرکدام دقیقاً یکبار در $T_2$ واقع می‌شوند. ابتدا فرض می‌کنیم که همه‌ی این $p$ رأس یا بیشتر در بخش یکسانی از $G_1$ واقع نشوند. آنگاه می‌توانیم دو نقطه $x$ و $y$ با تعداد تکرار $1$ را از دو بخش مختلف از $G_1$ انتخاب کنیم. چون یال $xy$ در $T_1$ واقع شده، باید در $T_2$ واقع شود. بنابراین $x$ و $y$ هر دو در یک بلوک از $T_2$ واقع می‌شوند، مثلاً $G'_1$ ، و در هیچ بلوک دیگر $T_2$ واقع نمی‌شوند. هر رأس در $G_1$ با حداقل یکی از رأس‌های $x$ و $y$ مجاور است، چون آن‌ها در دو بخش مختلف هستند. این یال‌ها باید در $T_2$ باشند، بنابراین هر رأس در $G_1$ در $G'_1$ نیز هست، یعنی، $V(G_1)=V(G'_1)$. حالتی که همه‌ی رأس‌ها با تکرار $1$ در یک بخش یکسان از $G_1$ واقع شوند را رد می‌کنیم. چون حداقل $p$ رأس‌ با تکرار $1$ وجود دارد، همه رأس‌ها در یک بخش $P$ از $G_1$ تعداد تکرار $1$ دارند. یکی از این رأس‌ها را انتخاب می‌کنیم، مثلاً $x$ ، و فرض می‌کنیم بلوکی از $T_2$ که شامل $x$ است، $G'_1$ باشد. در $T_1$ ، $x$ با هر رأس در $V(G_1)\setminus P$ مجاور است. پس $x$ باید با هر یک از این رأس‌ها در $T_2$ هم مجاور باشد. اما $G'_1$ تنها بلوکی از $T_2$ است که شامل $x$ است، پس $V(G_1)\setminus P \subseteq V(G'_1)$. فرض کنید $y$ هر عضوی از $P$ به جز $x$ باشد، و فرض کنید $G'_i$ بلوکی از $T_2$ شامل $y$ باشد. طبق استدلال بالا، $V(G_1) \setminus P \subseteq V(G'_i)$ است. توجه کنید که $G$ حداقل سه بخش دارد. می‌دانیم که $\vert V(G_1)\setminus P \vert \geq 2p$ بنابراین طبق قسمت دوم لم \ref{2.2.2} باید داشته باشیم که $G'_i =G'_1$ ؛ به عبارت دیگر، $y \in G'_1$. اما $y$ به دلخواه از $P$ انتخاب شده بود، بنابراین $P \subseteq V(G'_1)$. بنابراین $V(G_1) \subseteq V(G'_1)$ و پس دوباره $V(G_1) = V(G'_1)$ . این استدلال برای هر بلوک از $T_1$ برقرار است، پس نتیجه می‌شود که ترید $\lbrace T_1 ,T_2 \rbrace$ زنجیری است. \end{proof} قسمت دوم و مشکل‌تر استدلال نشان دادن این است که هیچ ترید زنجیری از حجم کمتر یا مساوی پنج وجود ندارد. \begin{theorem}\label{22.2.2} برای هر گراف $G= K_{n(p)}$ ، $(n \geq 2, p \geq 2)$ ، هیچ $-G$ ترید زنجیری از حجم $s \leq 5$ وجود ندارد. \end{theorem} \begin{proof} فرض کنید $\lbrace T_1 ,T_2 \rbrace$ یک $-G$ ترید زنجیری از حجم $s \leq 5$ است، که $T_1 = \lbrace G_1,G_2,\ldots, G_s \rbrace$ ، $T_2 = \lbrace G'_1,G'_2,\ldots, G'_s \rbrace$ ، و $V(G_{\alpha}) = V(G'_{\alpha})$ ، $(\alpha = 1,2,\ldots,s)$.\\ فرض کنید $I_{\alpha\beta}= V(G_{\alpha}) \cap V(G_{\beta})= V(G'_{\alpha}) \cap V(G'_{\beta})$ ، برای تمام $\alpha \neq \beta $ ، $(1 \leq \alpha ,\beta \leq s)$ است. که این مجموعه‌ها پایه‌ی استدلال این اثبات را تشکیل می‌دهند.\\ داریم $V(G_{\alpha}) = V(G'_{\alpha})$ ، $(\alpha = 1,2,\ldots,s)$ ، اما $ G_{\alpha} $ و $ G'_{\alpha} $ دقیقاً یال‌های یکسان نمی‌توانند داشته‌باشند(زیرا با تعریف ترید تناقض دارد)، به علاوه انتظار داریم که آن‌ها یال‌های زیادی مشترک داشته‌باشند. اگر یک یال $e$ در $ E(G_{\alpha}) $ باشد اما در $E( G'_{\alpha}) $ نباشد، آنگاه $e$ باید در یک بلوک دیگری از $T_2$ باشد. درنظربگیرید $e \in E(G_{\alpha}) ,E(G'_{\beta}) $ ( $e$ در هیچ بلوک دیگری از $T_1$ یا $T_2$ نمی‌تواند واقع شود). آنگاه گوییم $e$ "انتقال یافته" از $ G_{\alpha} $ به $G'_{\beta}$ است.\\ فرض کنید یک یال $e = ab$ انتقال یافته از یک $ G_{\alpha} $ به یک $G'_{\beta}$ است. با تنها این محدودیت که $\alpha \neq \beta$ . آنگاه $\lbrace a, b \rbrace \subset V(G_{\alpha})$ و $\lbrace a, b \rbrace \subset V(G'_{\beta})$ . چون ترید زنجیری است، نتیجه می‌شود که $\lbrace a, b \rbrace \subseteq I_{\alpha\beta}$ پس یال‌ها تنها می‌توانند از یک بلوک در $T_1$ به بلوکی در $T_2$ با مجموعه رأس‌های مشترک‌شان منتقل شوند.\\ طبق لم \ref{2.2.2} ، $\vert I_{\alpha\beta} \vert \leq p$ ؛ و حداقل یکی از $G_{\alpha} \langle I_{\alpha\beta} \rangle$ ، $G_{\beta} \langle I_{\alpha\beta} \rangle$ و یکی از $G'_{\alpha} \langle I_{\alpha\beta} \rangle$ ، $G'_{\beta} \langle I_{\alpha\beta} \rangle$ هیچ یالی ندارند. فرض می‌کنیم یک یال $e$ انتقال یافته از $ G_{\alpha} $ به $G'_{\beta}$ وجود دارد، پس $e \in G_{\alpha} \langle I_{\alpha\beta} \rangle ,G'_{\beta} \langle I_{\alpha\beta} \rangle$ است. بنابراین نه $G'_{\alpha} \langle I_{\alpha\beta} \rangle$ و نه $G_{\beta} \langle I_{\alpha\beta} \rangle$ هیچ یالی ندارند. نتیجه می‌شود که هیچ یالی از $G_{\beta}$ به $ G'_{\alpha} $ نمی‌تواند منتقل شود، پس انتقال یال‌ها یک‌طرفه است. به طور خلاصه:\\ (1) $\vert I_{\alpha\beta} \vert \leq p$ برای تمام $\alpha \neq \beta$. (2) اگر یک یال از $ G_{\alpha} $ به $G'_{\beta}$ انتقال یافته‌است، آنگاه $I_{\alpha\beta}$ درون یک بخش یکتا از $ G'_{\alpha} $ و یک بخش یکتا از $G_{\beta}$ است، اما شامل رأس‌هایی از حداقل دو بخش $ G_{\alpha} $ و حداقل دو بخش $G'_{\beta}$ است. (3) اگر یک یال انتقال یافته از $ G_{\alpha} $ به $G'_{\beta}$ باشد، آنگاه هیچ یالی از $G_{\beta}$ به $ G'_{\alpha} $ نمی‌تواند انتقال یابد.\\ یک بلوک دلخواه $G_i \in T_1$ را درنظربگیرید. چون $G_i \neq G'_i$ ، حداقل یک یال از $G_i$ به یک بلوک $G'_j \in T_2$ ، $(j \neq i)$ انتقال یافته‌است. طبق (2) ، می‌دانیم که $I_{ij}$ درون یک بخش $G'_i$ است، و درون یک بخش $G_j$ ، اما $I_{ij}$ شامل رأس‌هایی از حداقل دو بخش $G_i$ و حداقل دو بخش $G'_j$ است.\\ مثلاً $I_{ij}$ شامل رأس‌هایی از دو بخش $P_{i1}$ و $P_{i2}$ از $G_i$ است( ممکن است شامل رأس‌هایی از بخش‌های دیگر هم باشد)، و $I_{ij}$ یک زیر مجموعه یک بخش $P'_{i1}$ از $G'_i$ است. آنگاه $P'_{i1}$ شامل حداقل یک رأس از هریک از $P_{i1}$ و $P_{i2}$ است. چون $P_{i1}$ و $P_{i2}$ مجزا هستند و هر دو اندازه‌ی $p$ دارند، مانند $P'_{i1}$ ، $P'_{i1}$ نمی‌تواند شامل همه‌ی $P_{i1}$ یا همه‌ی $P_{i2}$ باشد؛ بنابراین $P'_{i1}$ یک افراز مناسب از $P_{i1}$ و $P_{i2}$ تعریف می‌کند.\\ می‌توانیم بنویسیم \begin{center} $P_{i1}=A_1 \cup B_1،$\\ $P_{i2}=A_2 \cup B_2.$\\ \end{center} که $A_1,A_2,B_1$ و $B_2$ دو به دو مجزا و غیر تهی هستند، که \begin{align} A_1 \subseteq P'_{i1}, \label{1}\\ A_2 \subseteq P'_{i1} , \label{2}\\ B_1 \cap P'_{i1} = \emptyset , \label{3}\\ B_2 \cap P'_{i1} = \emptyset . \label{4} \end{align} همچنین، چون \begin{equation} I_{ij} \subseteq P'_{i1} , \label{5} \end{equation} داریم \begin{align} B_1 \cap I_{ij} = \emptyset , \label{6}\\ B_2 \cap I_{ij} = \emptyset . \label{7} \end{align} مجموعه رأس‌های $A_1$ و $B_1$ در دو بخش مختلف از $G'_i$ هستند اما در یک بخش یکسان از $G_i$ واقع می‌شوند. بنابراین هر یال $ab$ ، که $a \in A_1$ ، $b \in B_1$ است، در $G'_i$ قرار دارد اما در $G_i$ نیست، پس باید از یک بلوک $T_1$ به $G'_i$ انتقال یابد. یکی از این یال‌ها را به دلخواه انتخاب می‌کنیم، مثلاً $a_1b_1$ ، و فرض کنید $G_r$ بلوکی باشد که $a_1b_1$ از آن انتقال یافته بود( یال‌های دیگر ممکن است از بلوک‌های متفاوت $T_1$ انتقال یافته باشند، اما ما فقط یک بلوک را انتخاب می‌کنیم). واضح است که $r \neq i$ است. هر یال انتقال یافته باید از بین رأس‌هایی در اشتراک مجموعه رأس‌ها باشد، پس $I_{ir}$ شامل رأس‌هایی از $A_1$ و $B_1$ است.\\ طبق (2) ، $I_{ir}$ درون یک بخش یکتا از $G'_r$ است، و درون یک بخش یکتا از $G_i$ ، اما شامل رأس‌هایی از حداقل دو بخش از $G_r$ و دو بخش از $G'_i$ است. در کل، چون $I_{ir}$ شامل رأس‌هایی از $A_1$ و $B_1$ (و بنابراین $P_{i1}$ )، است داریم $I_{ir} \subseteq P_{i1}$.\\ \begin{figure}[h] \centering \includegraphics[width=8cm]{bi1.jpg} \caption{ ارتباط بین $G_i$ ، $G'_i$ ، $G_j$ و $G'_j$ ، باتوجه به اینکه حداقل یک یال از $G_i$ به $G_j$ انتقال یافته‌است. } \end{figure} مشابهاً باید یک $G_l \in T_1$ وجود داشته باشد به‌طوری‌که حداقل یک یال $a_2b_2 $ ، که $a_2 \in A_2$ ، $b_2 \in B_2$ است، از $G_l$ به $G'_i$ انتقال یافته‌است، و $I_{il} \subseteq P_{i2}$ باشد.\\ حال رأس دلخواه $b$ در $B_1 \cup B_2$ را درنظربگیرید. بدون کم شدن از کلیت فرض کنید که $b \in B _1$ است. نقاطی در $A_1$ در همان بخشی از $G_i$ که $b$ است، هستند $(P_{i1})$ . اما طبق \eqref{1} و \eqref{3} ، آن‌ها در بخش‌های مختلفی از $G'_i$ هستند. چون هر بخش از هر بلوک یک اندازه‌ دارد، نتیجه می‌شود که به قرینه حداقل یک رأس وجود دارد، آن را $c$ می‌نامیم، به‌طوری‌که $b$ و $c$ در بخش‌های متفاوت از $G_i$ هستند اما در یک بخش از $G'_i$ . بنابراین یال $bc$ انتقال یافته از $G_i$ به یک بلوک از $T_2$ است، آن را $G'_k$ می‌نامیم. طبق (2) ، می‌دانیم که $I_{ik}$ درون تنها یک بخش از $G_k$ است و تنها یک بخش از $G'_i$ ، اما شامل یال‌هایی از بیشتر از یک بخش از $G'_k$ و $G_i$ است. پس $I_{ik} \subset P'_{i2}$ ، که $P'_{i2}$ یک بخش از $G'_i$ است( $P'_{i2} \neq P'_{i1}$ چون بنابر \eqref{3} ، $b \not\in P'_{i1}$ ).\\ حال ثابت می‌کنیم که $i,j,k,r,l$ متمایز هستند. طبق تعریف، $i$ متمایز از بقیه است، چون بلوک‌های دیگر در شرایط انتقال یال‌ها به $G'_i$ یا انتقال از $G_i$ ،تعریف شده بودند. یادآوری می‌کنیم که یال‌ها انتقال یافته از $G_i$ به $G'_j$ و $G'_k$ هستند، و از $G_r$ و $G_l$ به $G'_i$ . بنابراین، طبق (3) ، $j$ و $k$ از $r$ و $l$ متمایز هستند. نشان دادیم که $I_{ir} \subset P_{i1}$ و $I_{il} \subset P_{i2}$ . نتیجه می‌دهد که $I_{ir} \neq I_{il}$ و بنابراین $r \neq l$ . مشابهاً $I_{ij} \subset P'_{i1}$ و $I_{ik} \subset P'_{i2}$ ، پس $j \neq k$ . بنابراین $i,j,k,r,l$ همگی متمایز هستند.\\ چون ما وجود حداقل پنج بلوک در هر یک از $T_1$ و $T_2$ استنباط کرده ایم، $s \geq 5$ . اما ما تنها ترید‌هایی از حجم $s \leq 5$ را در نظر می‌گیریم، پس $s=5$ . بنابراین $\lbrace i,j,k,r,l \rbrace$ یک تجدید آرایش از $\lbrace 1,2,3,4,5 \rbrace$ است، و هیچ بلوکی در $T_1$ و $T_2$ به ترتیب به غیر از $G_i,G_j,G_k,G_r,G_l$ و $G'_i,G'_j,G'_k,G'_r,G'_l$ وجود ندارد. با استفاده از این آگاهی، می‌توانیم دوباره استدلال قبل را استفاده کنیم و ساختار ترید را دقیق‌تر استنباط کنیم.\\ به یاد بیاورید که قبلاً وجود $ G_k $ را با درنظرگرفتن یک نقطه دلخواه $ b \in B _1 \cap B _2 $ استنباط کرده بودیم، و نشان می‌دهد که یک یال شامل $b$ باید از $G_i$ به یک بلوک $T_2$ انتقال یابد، که ما آن را $G'_k$ می‌نامیم(پس $b \in I_{ik}$ ). اما با توجه به هر نقطه دیگر $b_0 \in B_1 \cup B_2$ ، یک یال شامل $b_0$ باید مشابهاً از $G_i$ به یک بلوک از $T_2$ انتقال یابد. طبق (3) ، این بلوک $G'_r$ یا $G'_l$ نمی‌تواند باشد؛ و آن $G'_j$ نمی‌تواند باشد، چون طبق \eqref{6} و \eqref{7} ، $b _0 \not\in I_{ij}$ است. بنابراین یک یال شامل $ b _0 $ باید از $G_i$ به $G'_k$ انتقال یابد. نتیجه می‌دهد که $b_0 \in I_{ik}$ ، و چون $b_0$ به دلخواه انتخاب شده بود، $B _1 \cup B_2 \subseteq I_{ik}$ .با یک استدلال مشابه، $A_1 \cup A_2 \subseteq I_{ij}$ است.\\ اما\\ \[\vert B_1 \cup B_2 \vert + \vert A_1 \cup A_2 \vert = \vert P_{i1} + \vert P_{i2} \vert =2p. \] بنابراین \[ \vert I_{ij} \vert + \vert I_{ik} \vert \geq 2p ,\] تساوی برقرار است اگر و فقط اگر $ A_1 \cup A_2 = I_{ij} $ و $B_1 \cup B_2= I_{ik}$ . اما طبق (1) ، $ \vert I_{ij} \vert , \vert I_{ik} \vert \leq p $ . در نتیجه \begin{center} $\vert I_{ij} \vert= \vert I_{ik} \vert =p,$\\ $ A_1 \cup A_2 = I_{ij}, $\\ $B_1 \cup B_2= I_{ik}.$\\ \end{center} چون $\vert I_{ij} \vert= \vert I_{ik} \vert =p $ است، $I_{ij} \subseteq P'_{i1}$ و $I_{ik} \subseteq P'_{i2}$ ، همچنین داریم $I_{ij} = P'_{i1}$ و $I_{ik} = P'_{i2}$.\\ می‌توانیم یک نتیجه مشابه برای $I_{ir}$ و $I_{il}$ بدست بیاوریم. یاد آوری می‌کنیم که $I_{ir} \subseteq P_{i1}=A_1 \cup B_1$ و $I_{il} \subseteq P_{i2}=A_2 \cup B_2$ . رأس‌های دلخواه $a \in A_1$ ، $b \in B_1$ را درنظربگیرید. یال $ab$ در $G'_i$ واقع می‌شود اما در $G_i$ واقع نمی‌شود، پس آن باید از یک بلوک $T_1$ به $G'_i$ انتقال یابد. چون $a,b \in P_{i1}$ و $I_{il} \subseteq P_{i2}$ است، $G_l$ رد می‌شود، و (3) $G_j$ و $G_k$ را رد می‌کند. بنابراین $ab$ از $G_r$ انتقال یافته‌است، و $\lbrace a,b \rbrace \in I_{ir}$ . اما $a$ و $b$ دلخواه بودند، پس $A_1 \cup B _1 \subseteq I_{ir}$ . بنابراین $P_{i1} =A_1 \cup B _1= I_{ir}$ ، و $\vert I_{ir} \vert =p$ . به همین ترتیب $P_{i2}=A_2 \cup B _2=I_{il}$ ، و $\vert I_{il} \vert =p$.\\ به طور خلاصه، \begin{center} $\vert I_{ij} \vert =\vert I_{ik} \vert =\vert I_{ir} \vert =\vert I_{il} \vert =p,$\\ $ I_{ij}=A_1 \cup A_2 = P'_{i1},$\\ $ I_{ik}=B_1 \cup B_2=P'_{i2},$\\ $ I_{ir} =A_1 \cup B _1=P_{i1},$\\ $I_{il}=A_2 \cup B _2=P_{i2}.$\\ \end{center} \begin{figure}[t] \centering \includegraphics[width=16cm]{bi2.jpg} \caption{ارتباط بین $G_i$ و $G'_i$ و بلوک‌های دیگر $T_1$ و $T_2$ ، به علاوه ارتباط بین $G_j$ ، $G'_j$ ، $G_k$ و $G'_k$ ، با توجه به یال‌های انتقال یافته از $G_j$ به $G'_k$.} \label{bi2} \end{figure} حال ساختار تریدی که در شکل \ref{bi2} نشان داده شده‌است را استنباط می‌کنیم، به جز برای $I_{jk}$ که در زیر بحث می‌شود. مشاهده می‌کنید که $V(G_i)=V(G'_i)$ ، $2p$ از رأس‌هایش ( $A_1 \cup A_2 \cup B_1\cup B_2$ )تعداد تکرار $3$ یا بیشتر دارد، و تمام رأس‌های دیگر تعداد تکرار $1$ دارند(به عنوان مثال، یک رأس در $A_1$ در $V(G_i)$ ، $V(G_j)$ و $V(G_r)$ است). در حقیقت ما یک ساختار دقیق کامل استنباط کرده ایم. به طور خاص، توجه کنید:\\ (4) برای تمام $\alpha \neq i$ یا، یک یا چند یال از $G_i$ به $G'_{\alpha}$ انتقال یافته‌اند یا، یک یا چند یال از $G_{\alpha}$ به $G'_i$ انتقال یافته‌اند. (5) اگر یک یا چند یال از $G_i$ به یک $G'_{\alpha}$ منتقل ‌شوند، و یک یا چند یال از یک $G_{\beta}$ به $G'_i$ منتقل شوند، آنگاه $I_{i\alpha} \cap I_{i\beta} \neq \emptyset$. (6) برای هر $\alpha \neq i $ ، $\vert I_{\alpha i} \vert =p$.\\ اما بلوک $G_i$ به دلخواه انتخاب شده بود، پس (4) ، (5) و (6) برای هر بلوک انتخاب شده،علاوه بر $G_i$ بکار می‌رود.\\ $G_j$ و $G_k$ را درنظربگیرید. با استفاده از (4) ، بدون کم شدن از کلیت فرض کنیدکه یک یا چند یال از $G_j$ به $G'_k$ منتقل شوند. آنگاه طبق (5) ، $I_{jk}$ شامل حداقل یک رأس از $I_{ij} = A_1 \cup A_2$ است؛ آن را $a$ می‌نامیم. طبق (2) و (6) ، \begin{center} $B_1 \cup B_2 =I_{ik}=P_{k1},$\\ $a \in I_{jk}=P_{k2},$\\ \end{center} که $P_{k1}$ و $P_{k2}$ بخش‌هایی از $G_k$ هستند. می‌دانیم $P_{k1} \neq P_{k2}$ چون $a \not\in B _1 \cup B_2$ . طبق تعریف، $a \in A_1 \cup A_2$ است. اما اگر $a \in A_1$ ، آنگاه یال‌های بین $a$ و رأس‌هایی در $B_2$ در هر دوی $G_i$ و $G_k$ واقع می‌شود، در حالی‌که اگر $a \in A_2$ ، آنگاه یال‌های بین $a$ و رأس‌هایی در $B_1$ در هر دوی $G_i$ و $G_k$ واقع می‌شود. این یک تناقض است، بنابراین ترید وجود ندارد. \end{proof} با ترکیب دو قضیه بالا اولین نتیجه اصلی‌مان را داریم: \begin{theorem} فرض کنید که $G= K_{n(p)}$ ، $n \geq 3)$ ، $(p \geq 2$ است. آنگاه هیچ $-G$ ترید از حجم کمتر یا مساوی $min(n,5)$ وجود ندارد. \end{theorem} \begin{proof} از قضیه‌های بالا نتیجه می‌شود. \end{proof} \begin{lemma}\label{1.1.2} برای هر عدد صحیح $p$ یک $-K_{3(p)}$ ترید از حجم $4$ وجود دارد. \end{lemma} \begin{proof} واضح است یک $K_{3(1)}=K_3$ ترید از حجم $4$ روی هشت وجهی $H=K_{3(2)}$ وجود دارد. حال نقاط را منفجر می‌کنیم: هر رأس $a$ از $H$ را با یک مجموعه $V_a$ از اندازه $p$ جایگزین می‌کنیم، و هر یال $ab$ از $H$ را با $p^2$ یال از یک کپی $K_{p,p}$ روی دو بخش $V_a , V_b$ . (البته، مطمئنیم که $V_x$ ها دو به دو مجزا هستند.) آنگاه هر کپی از $K_{3(1)}$ در $H$ یک کپی از $K_{3(p)}$ می‌شود. \end{proof} \begin{lemma}\label{1.3.5} فرض کنید که یک $K_{m(2)}$ ترید زنجیری از حجم $s$ وجود دارد. آنگاه برای هر $n \geq m$ ، یک $K_{n(2)}$ ترید زنجیری از حجم $s$ وجود دارد.\\ \end{lemma} \begin{proof} فرض کنید $\{T_1,T_2\}$ یک $-K_{m(2)}$ ترید زنجیری روی گراف $H$ است،که $T_1=\lbrace G_1, G_2, \ldots , G_s \rbrace $ با زوج $T_2= \lbrace G'_1, G'_2, \ldots , G'_s \rbrace $ . برای هر $1 \leq i \leq s$ ، فرض کنید $W_i$ یک مجموعه از $2n-2m$ رأس جدید است، که از یکدیگر، و از $V(H)$ مجزا هستند. فرض کنید $M_i$ گراف حاصل روی مجموعه رأس‌های $W_i \cup V(G_i)$ است به‌طوری‌که: روی $W_i$ ، یک کپی از $K_{(n-m)(2)}$ را قرار دهیم، و هر رأس $W_i$ به هر رأس $V(G_i)$ با یک یال وصل کنیم. فرض کنید $N_i$ (متناظراً $N'_i$ ) گراف بدست آمده از $M_i$ با اضافه کردن یال‌های $G_i$ ( متناظراً یال‌های $G'_i$ )است. آنگاه $\lbrace N_1 ,N_2 , \ldots ,N_s \rbrace $ یک $K_{n(2)}$ ترید زنجیری از حجم $s$ با زوج $\lbrace N'_1 ,N'_2 , \ldots ,N'_s \rbrace $ است.\\ \end{proof} حال یک $-C_4$ ترید زنجیری( یعنی $K_{2(2)}$ ) از حجم $s \geq 6$ به جز $s=7$ و یک $K_{3(2)}$ ترید زنجیری از حجم $7$ را می‌سازیم. \begin{figure}[t] \centering \includegraphics[width=5cm]{bib1.jpg} \caption{ } \label{bib.1} \end{figure} \begin{figure}[t] \centering \includegraphics[width=8cm]{bib2.jpg} \caption{ } \label{bib.2} \end{figure} \begin{lemma}\label{1.3.6} فرض کنید $P$ یک گراف مسطح ساده با دقیقاً $s$ وجه، هر یک با $4$ یال است. یک گراف $H$ را با اضافه کردن $2s$ یال به $P$ به صورت زیر تشکیل می‌دهیم: برای هر وجه $F$ از $P$ ، اگر یال‌های $ab , bc , cd ,da$ مرز $F$ هستند، یال‌های $ac$ و $bd$ را اضافه می‌کنیم. اگر $H$ ساده باشد، آنگاه یک $-C_4$ ترید زنجیری روی $H$ از حجم $s$ وجود دارد. \end{lemma} \begin{proof} توجه می‌کنیم که $P$ دو بخشی است زیرا هر دور در $P$ از طول زوج است. فرض کنید $(A,B)$ یک افراز دو بخشی از $V(P)$ است. هر وجه از $P$ را به صورت شکل \ref{bib.1} درنظربگیرید. که $a_1, a_2 \in A$ و $b_1 ,b_2 \in B$.\\ فرض کنید $G_F$ و $G'_F$ مانند شکل \ref{bib.2} داده شده‌اند.\\ آنگاه $T_1=\lbrace G_F \vert\; \text{یک وجه ‌است} F\rbrace $ ، و زوج آن $T_2=\lbrace G'_F \vert\; \text{یک وجه است} F \rbrace $ ترید مورد نظرمان را تشکیل می‌دهند. \end{proof} \begin{lemma}\label{1.3.7} یک $-C_4$ ترید زنجیری از حجم $s$ برای هر $s \geq 6$ به جز $s=7$ وجود دارد. \end{lemma} \begin{proof} برای اثبات فقط باید گراف‌های مورد نیاز را بسازیم و از لم \ref{1.3.6} استفاده کنیم.\\ فرض کنید $t \geq 3$ . با یک نشاندن مسطح از یک دور $C$ با $2t$ رأس، روی مجموعه رأس‌های $ \mathbb{Z}_{2t} $ و یال‌های $(i)(i+1)$ ، $( i \in \mathbb{Z}_{2t}) $ شروع می‌کنیم. یک رأس $ \alpha $ در درون $ C $ اضافه می‌کنیم، که مجاور با رأس‌های $ 2i $ ، برای $ (0 \leq i < t) $ است. یک رأس $ \beta $ در داخل $ C $ اضافه می‌کنیم، که مجاور با رأس‌های $ 2i+1 $ ، برای $( 0 \leq i < t )$ است. پس گراف حاصل، یک گراف مسطح با $2t$ وجه هریک با $4$ یال است، پس طبق لم \ref{1.3.6} ترید ازحجم $ s=2t \geq 6 $ ، برای $s$ های زوج وجود دارد.\\ اگر $ t \geq 4 $ ، گراف بالا را به صورت زیر تنظیم می‌کنیم: یال $ \alpha2 $ را حذف می‌کنیم. داخل وجه حاصل با شش یال، محدود به دور $ (\alpha ,0,1,2,3,4) $ ، یک رأس جدید $ \alpha' $ قرار می‌دهیم، که مجاور با رأس‌های $ 0, 2 $ و $4$ است. سپس لم برای تمام $ s = 2t+1 \geq 9 $ فرد نتیجه می‌شود. ( به سادگی می‌بینیم که این ساختار اگر $ s = 7 $ باشد شکست می‌خورد.) \end{proof} \begin{lemma}\label{1.3.8} یک $-K_{3(2)}$ ترید زنجیری از حجم $7$ وجود دارد. \end{lemma} \begin{proof} گراف اساسی را $K_{7(2)}$ درنظربگیرید و ساختار آن به شرح زیر است : با گراف کامل روی مجموعه رأسهای $ \mathbb{Z}_{7} \times \mathbb{Z}_{2} $ شروع می‌کنیم، و یال‌های $(i, 0)(i, 1)$ ، $(i \in \mathbb{Z}_{7})$ را حذف می‌کنیم.\\ فرض کنید $K$ گراف کامل با مجموعه رأس‌های $\lbrace (0,0), (2, 1), (1, 0), (5, 1), (3, 0), (4, 1)\rbrace$ است. برای $G_1$ ، یال‌های $(0,0)(2, 1)$ ، $ (1, 0)(5, 1)$ و $ (3, 0)(4, 1)$ را از $K$ حذف می‌کنیم. برای $G'_1$ ، یال‌های $(2, 1)(1,0)$ ، $ (5, 1)(3, 0)$ و $ (4, 1)(0, 0)$ را از $K$ حذف می‌کنیم. این دو بلوک را (به پیمانه $(7,-)$ ) برای باقی‌مانده‌ی ترید بسط می‌دهیم. \end{proof} بنابراین با استفاده از لم \ref{1.3.5} یک $-K_{n(2)}$ ترید زنجیری از هر حجم $s \geq 6$ برای $n \geq 3$ وجود دارد. به سادگی می‌توانیم ساختار قبل را برای حالتی که $ G $ گراف چندبخشی کامل با $ n \geq 3 $ بخش، که هر یبخش از اندازه $ p \geq 3 $ است، که با $K_{n(p)}$ نشان می‌دهیم، تعمیم دهیم. \begin{lemma}\label{1.4.1} فرض کنید یک $-K_{m(p)}$ ترید زنجیری از حجم $ s $ وجود دارد. آنگاه، برای هر $ n \geq m $ یک $-K_{n(p)}$ ترید زنجیری از حجم $ s $ وجود دارد. \end{lemma} \begin{lemma}\label{1.4.2} یک $-K_ {2(p)} = K_{p,p} $ ترید زنجیری از حجم $ s $ برای هر $ s \geq 6 $ به جز احتمالاً $s = 7$ وجود دارد.\\ \end{lemma} \begin{proof} گراف $H$ را همان گراف اساسی ترید در ساختار لم‌های \ref{1.3.6} و \ref{1.3.7} درنظربگیرید، که $(A,B)$ یک افراز از رأس‌های $H$ تعریف می‌کند. $H^+$ را به شرح زیر تشکیل می‌دهیم: هر رأس $a \in A$ را با یک مجموعه $V_a$ از $p-1$ رأس جایگزین می‌کنیم. هر یال $ab$ از $H$ ، که $a \in A$ و $b \in B $ ، را با $p-1$ یال، برای هر یال بین یک رأس از $V_a$ و $b$ ، جایگزین می‌کنیم. و هر یال $ac$ از $H$ ، که $a,c \in A$ ، را با $(p-1)^2$ یال، برای هر یال بین یک رأس از $V_a$ و یک رأس از $V_c$ ، جایگزین می‌کنیم. (رأس‌های $B$ رأس‌های $H^+$ باقی‌می‌ماند، و یال‌های $H$ با دو انتها در $B$ یال‌های $H^+$ باقی‌می‌ماند.) آنگاه هر کپی از $C_4$ در یک نیمه ترید روی $H$ (یا در زوج آن) یک کپی از $K_{2(p)}=K_{p,p}$ در $H^+$ می‌شود. \end{proof} \begin{lemma}\label{1.4.3} یک $ K_{3(p)} $ ترید زنجیری از حجم $ 7 $ وجود دارد. \end{lemma} \begin{proof} برای اثبات هر رأس $ a \in A = \lbrace (i,0) \vert\; i \in \mathbb{Z}_7 \}$ در ساختار لم \ref{1.3.8} را به مجموعه‌ای از $ p-1 $ رأس $ V_a $ منفجر می‌کنیم، و ماننداثبات لم \ref{1.4.2} پیش می‌رویم. \end{proof} بنابراین با استفاده از لم \ref{1.4.1} یک $K_{n(p)}$ ترید زنجیری از هر حجم $s \geq 6$ برای $n \geq 3$ و $p \geq 2$ وجود دارد. \subsubsection{حالت‌های خاص} حال حالت‌های باقی‌مانده را برای گراف $K_{n(p)}$ حل می‌کنیم. ابتدا نشان می‌دهیم که یک ترید از حجم $5$ ، وقتی‌که $n=3$ است، وجود دارد(البته این ترید زنجیری نمی‌تواند باشد). این موضوع براساس ساختار زیر برای حالت $p=2$ است که با استفاده از جستجوی کامپیوتری پیدا شده‌است. \begin{theorem} گراف $K_{3(2)}$ یک ترید از حجم $5$ دارد. \end{theorem} \begin{proof} شکل \ref{bi3} را ببینید. که در آن مجموعه بنیان $\{0,1,2,\ldots,13\}$ درنظرگرفته شده‌است، و رأس‌ها به دو گروه از هفت رأس تقسیم شده‌اند(هفت رأس زوج و هقت رأس فرد)، به‌طوری‌که هر بخش از هر بلوک‌ شامل یک رأس از هر گروه است. $T_1=\{G_1,G_2,G_3,G_4,G_5\}$ و $T_2=\{G'_1,G'_2,G'_3,G'_4,G'_5\}$ است. \end{proof} \begin{figure}[t] \centering \includegraphics[width=12cm]{bi3.jpg} \caption{یک$-K_{3(2)}$ترید از حجم$5$ } \label{bi3} \end{figure} حال این ترید را به یک $K_{3(p)}$ ترید تعمیم می‌دهیم. \begin{theorem} گراف $K_{3(p)}$ یک ترید از حجم $5$ ، برای تمام $p \geq 2$ دارد. \end{theorem} \begin{proof} اثبات با استفاده از ساختار قبل است. هر رأس فرد در ترید نشان داده شده در شکل \ref{bi3} را با یک مجموعه از $p-1$ رأس جایگزین می‌کنیم. چون هر بخش از هر بلوک از $T_1$ و $T_2$ شامل یک رأس زوج و یک رأس فرد است، نتیجه یک $-K_{3(p)}$ ترید از حجم $5$ است. \end{proof} حال عدم وجود درحالت خاص بعدی را نشان می‌دهیم، وقتی‌که چهار بخش وجود دارد.\\ \begin{theorem} هچ $-K_{4(p)}$ تریدی از حجم $5$ وجود ندارد. \end{theorem} \begin{proof} فرض کنید گراف $G=K_{4(p)}$ ، یک ترید $\lbrace T_1, T_2 \rbrace$ از حجم $5$ دارد، که $T_1 =\lbrace G_1,G_2,G_3,G_4,G_5 \rbrace$ ، $T_2 =\lbrace G'_1,G'_2,G'_3,G'_4,G'_5 \rbrace$ است. حالتی که یک بلوک در $T_1$ ، مثلاً $G_1$ ، هیچ رأس منفرده (رأسی از تعداد تکرار $1$ )ندارد را درنظربگیرید، یعنی، هر رأس $G_1$ ، در حداقل یک بلوک دیگر از $T_1$ واقع شود. طبق قسمت دوم لم \ref{2.2.2} ، $G_1$ حداکثر در $p$ رأس با هر یک از چهار بلوک دیگر $T_1$ اشتراک دارد. چون $G_1$ ، $4p$ رأس دارد، تنها راه ممکن این است که $G_1$ دقیقاً $p$ رأس با هر یک از بلوک‌های دیگر از $T_1$ اشتراک داشته باشد. فرض کنید $G_1$ شامل یک رأس $v$ با تعداد تکرار $3$ یا بیشتر باشد. آنگاه $v$ برای یک $G_j$ و $G_k$ ای در $T_1\setminus \lbrace G_1 \rbrace$ ، در هر دوی $G_j$ و $G_k$ واقع می‌شود. حال $G_1$ ممکن است تا $p$ رأس با هر یک از $G_j$ و $G_k$ اشتراک داشته باشد اما چون $v$ در هر سه بلوک مشترک است، $G_1$ حداکثر $ 1+(p-1)+(p-1)=2p-1 $ رأس که یا در $G_j$ یا در $G_k$ نیز واقع هستند، می‌تواند داشته باشد. پس حداقل $2p+1$ رأس دیگر در $G_1$ باقی می‌ماند، پس نشان می‌دهد که حداقل یک رأس وجود دارد که فقط در $ G_1 $ واقع می‌شود، یعنی حداقل یک رأس منفرده در $G_1$ وجود دارد، که یک تناقض است. بنابراین اگر هیچ رأس منفرده‌ای وجود نداشته باشد، آنگاه هر رأس در $G_1$ باید تعداد تکرار $2$ داشته‌باشند.\\ حال حالت مکمل را در نظر می‌گیریم که یک بلوک از $T_1$ ، مثلاً $G_1$ ، شامل یک رأس منفرده، $s_0$ باشد. آنگاه $s_0$ در یک بلوک از $T_2$ ، مثلاً $G'_1$ ، نیز واقع می‌شود، و $s_0$ در هیچ بلوک دیگری از $T_1$ یا $T_2$ واقع نمی‌شود. فرض کنید $G_1$ بخش‌های $P_{11}, P_{12} , P_{13} , P_{14}$ را دارد، و $G'_1$ بخش‌های $P'_{11}, P'_{12} , P'_{13} , P'_{14}$ را دارد، که $s_0 \in P_{11} , P'_{11}$ . فرض کنید $A = P_{12} \cup P_{13}\cup P_{14}$ . در $G_1$ ، رأس $s_0$ با هر یک از $3p$ رأس از $A$ مجاور است. چون این یال‌ها باید در $T_2$ نیز واقع شوند و $G'_1$ تنها بلوکی از $T_2$ است که شامل $s_0$ است، نتیجه می‌شود که $ P'_{12} \cup P'_{13}\cup P'_{14} =A$ است. یک رأس $t$ در $P_{11} \setminus \lbrace s_0 \rbrace$ را درنظربگیرید. فرض کنید که $t \not\in P'_{11} \setminus \lbrace s_0 \rbrace$ ، و $t$ با یک $t'$ جایگزین شده‌است، $t'\in P'_{11}\setminus \lbrace s_0 \rbrace$ ، $t' \not\in P_{11}\setminus \lbrace s_0 \rbrace$ (نشان می‌دهیم که این منجر به یک تناقض می‌شود). در $T_1 $ ، رأس $t$ با هر رأس $A$ مجاور است، اما $t \not\in V(G'_1)$ . بنابراین $3p$ یال باید بین $t$ و رأس‌های $A$ در بلوک‌های $T_2$ به غیر از بلوک $G'_1$ واقع شود؛ یعنی، در بلوک‌های $G'_4 ,G'_3 , G'_2$ و $G'_5$ . چون تمام رأس‌های $A$ در $G'_1$ واقع می‌شوند، طبق قسمت دوم لم \ref{2.2.2} حداکثر $p$ رأس از $A$ ( و بنابراین حداکثر $p$ یال بین $t$ و رأس‌های $A$ ) در هر $G'_2 ,G'_3 , G'_4$ و $G'_5$ واقع می‌شود. بنابراین $3p$ یال بین $t$ و رأس‌های $A$ روی حداقل سه بلوک از $G'_2 ,G'_3 , G'_4$ و $G'_5$ پخش شده‌اند. بنابراین $t$ تعداد تکرار سه یا بیشتر دارد؛ فرض کنید $t \in G'_2 ,G'_3 , G'_4$ . براساس تقارن $t'$ نیز تعداد تکرار $3$ یا بیشتر دارد، و بنابراین طبق اصل لانه کبوتر حداقل یکی از $G'_2 ,G'_3 $ یا $ G'_4$ شامل $t'$ است؛ فرض کنید $t' \in G'_2$.\\ بلوک $G'_1$ شامل تمام یال‌های بین $t'$ و رأس‌های در $A$ است؛ این یال‌ها در $T_2$ نمی‌توانند تکرار شوند، پس $G'_2$ شامل $p-1$ رأس از $A$ است( آن‌ها باید در همان بخش از $G'_2$ که $t'$ است باشند) و بنابراین حداکثر $p-1$ یال بین $t$ و رأس‌های $A$ است. چون $G'_3$ و $G'_4$ هر یک شامل حداکثر $p$ چنین یال‌هایی است، نتیجه می‌شود که $G'_5$ باید شامل حداقل $3p$ یال بین $t$ و رأس‌های $A$ باشد. بنابراین $t$ ، و به قرینه $t'$ ، تعداد تکرار $4$ دارد( تعداد تکرار $5$ رد شده‌است چون $t \not\in P'_{11}$ ، $t' \not\in P'_{11}$ ).\\ پس همگی $G'_4 ,G'_3 , G'_2$ و $G'_5$ شامل $t$ هستند، و حداقل سه تا از آن‌ها، مثلاً $G'_2 ,G'_3 $ و $ G'_4$ ، شامل $t'$ هستند. فرض کنید یکی از این سه بلوک، مثلاً $G'_2$ ، شامل یک یال بین $t$ و یک رأس $v \in A$ باشد. یال $t'v$ در $G'_1$ واقع شده، پس $t'$ و $v$ در یک بخش از $G'_2$ هستند. بنابراین $G'_2$ شامل یال $tt'$ است. اما حداکثر یکی از $G'_2 ,G'_3 $ یا $ G'_4$ می‌توانند شامل این یال باشند، پس حداکثر یکی از این‌ها می‌تواند شامل هر یال بین $t$ و یک رأس $v \in A$ باشد. این فقط دوبلوک از $T_2$ را کنار می‌گذارد( $G'_5$ و یکی از $G'_2 ,G'_3 $ یا $ G'_4$ ) که می‌تواند شامل یال‌هایی بین $t$ و رأس‌های $A$ باشد، که قبلاً دیدیم کافی نیست. این یک تناقض می‌دهد، پس هیچ رأسی که در $P_{11} \setminus \lbrace s_0 \rbrace$ واقع شود اما در $P'_{11} \setminus \lbrace s_0 \rbrace$ واقع نشود، وجود ندارد. بنابراین، با توجه به این فرض که $G_1$ شامل حداقل یک رأس منفرده است، می‌دانیم برای یک بلوک $G'_1$ از $T_2$ ، $V(G_1)=V(G'_1)$.\\ با درنظرگرفتن حالتی که یک بلوک هیچ رأس منفرده ندارد، و نیز حالتی که آن بلوک حداقل یک رأس منفرده دارد، ما نشان دادیم که برای هر بلوک $G_i$ ، یا $G_i$ دقیقاً $p$ رأس با هر بلوک دیگر اشتراک دارد و هر رأس در $G_i$ تعداد تکرار $2$ دارد، یا $V(G_i) = V(G'_i)$ برای یک $G'_i \in T_2$ ، یاهر دو. بنابراین می‌توانیم ساختار بلوک را به دو حالت متمایز بشکنیم:\\ $(a)$ $V(G_i)=V(G'_i)$ برای یک $G'_i \in T_2$.\\ $(b )$ $G_i$ دقیقاً $p$ رأس با هر بلوک دیگر در $T_1$ اشتراک دارد، هر رأس در $G_i$ تعداد تکرار $2$ دارد، و $(a)$ برقرار نیست.\\ فرض کنید $G_i$ هر بلوکی از نوع $(b )$ باشد، و $G_j$ هر بلوک دیگری از $T_1$ باشد. آنگاه $Q = V(G_i) \cap V(G_j)$ اندازه $p$ دارد. چون $p \geq 2$ می‌توانیم رأس‌های $x , y \in Q$ را انتخاب کنیم( $x , y$ هر کدام تعداد تکرار $2$ دارند چون در $G_i$ هستند).چون یال $xy$ تنها یک‌بار می‌تواند در $T_1$ واقع شود، $x$ و $y$ باید یا در یک بخش از $G_i$ واقع شوند یا در یک بخش از $G_j$ ، یا هر دو. بنابراین مجموعه $A$ از رأس‌های مجاور با هر دوی $x$ و $y$ شامل سه بخش از $G_i$ و حداقل دو بخش از $G_j$ ، یا برعکس است. بنابراین اندازه مجموعه $A$ بیشتر یا مساوی $5p$ است. چون $x$ و $y$ هر یک تعداد تکرار $2$ دارند می‌توانیم فرض کنیم $x \in G'_r , G_s$ ، $y \in G'_t , G'_u$ است، که $G'_r , G_s ,G'_t , G'_u$ بلوک‌هایی از $T_2$ هستند که $G'_r \neq G'_s$ و $ G'_t \neq G'_u $ . تمام یال‌های بین $x$ یا $y$ و رأس‌های $A$ باید در $T_2$ واقع شوند، بنابراین $A \subseteq G'_r \cup G'_s$ و $A \subseteq G'_t \cup G'_u$.\\ فرض کنید $t \not\in \lbrace r,s \rbrace$ (ما باید نشان دهیم که این منجر به یک تناقض می‌شود). چون $G'_t$ شامل حداکثر $p$ رأس از هر یک از $G'_r$ و $G'_s$ است و تمام رأس‌های $A$ در این دو بلوک هستند، $G'_t$ حداکثر می‌تواند شامل $2p$ رأس از $A$ باشد. بنابراین $G'_u$ شامل حداقل $3p$ رأس از $5p$ رأس $A$ است، و پس $u \in \lbrace r,s \rbrace$ . فرض کنید $u=s$ . حال $G'_u = G'_s$ حداکثر می‌تواند شامل $4p-2$ رأس از $A$ باشد، چون آن شامل هردوی $x$ و $y$ است، که در $A$ نیستند. تعداد رأس باقی‌مانده در $A$ بیشتر یا مساوی $p+2$ است، که باید در هردوی $G'_r$ و $G'_t$ واقع شوند، اما این موضوع با قسمت دوم لم \ref{2.2.2} تناقض دارد. بنابراین با این تناقض $t \in \lbrace r,s \rbrace$ . به همین ترتیب $u\in \lbrace r,s \rbrace$ ؛ پس $\lbrace G'_r ,G'_s \rbrace = \lbrace G'_t , G'_u \rbrace$ . یعنی، $x$ و $y$ هر کدام در دو بلوک یکسان از $T_2$ واقع می‌شوند.پس همه $p$ رأس در $Q$ در دو بلوک یکسان از $T_2$ واقع می‌شوند، یا $Q = V(G_i) \cap V(G_j) = V(G'_k) \cap V(G'_l)$ برای یک $G'_k , G'_l \in T_2$.\\ ابتدا این نتیجه را در حالتی که برخی بلوک‌ها از نوع $(a)$ و برخی از نوع $(b)$ هستند، استفاده می‌کنیم. فرض کنید $G_i$ از نوع $(b)$ و $G_j$ از نوع $(a)$ باشد، و فرض کنید $Q= V(G_i) \cap V(G_j)$ مانند قبل است. با استفاده از نتیجه بالا و این واقعیت که $G_j$ از نوع $(a)$ است، برای دو بلوک $G'_k$ و $G'_j$ در $T_2$ ، می‌دانیم که $Q= V(G'_k) \cap V(G'_j)$ و $V(G_j)=V(G'_j)$ ، ( هیچ رأس $Q$ در بلوک دیگری از $T_2$ واقع نمی‌شود چون همه آن‌ها تعداد تکرار $2$ دارند). یک رأس $ v $ در $ G_i $ را درنظربگیرید، که $v \not\in Q$ . $p$ رأس از $Q$ همه نمی‌توانند در همان بخشی از $G_i$ که $v$ است باشند، پس حداقل یک یال بین $v$ و یک رأس در $Q$ وجود دارد. این یال باید در $T_2$ نیز واقع شود، بنابراین $v$ یا در $G'_k$ یا در $G'_j$ است. اما اگر $v \in G'_j$ آنگاه $v \in G_j$ و بنابراین $v \in Q$ ، درتناقض با فرض‌مان است. بنابراین $v \in G'_k$ . اما $v$ از $V(G_i) \ Q$ به دلخواه انتخاب شده بود، بنابراین $V(G_i) \ Q \subset V(G'_k)$ . چون $Q \subset V(G'_k)$ همچنین، $V(G_i) = V(G'_k)$ . بنابراین $G_i$ از نوع $(a)$ است، تناقض با این فرض است که آن از نوع $(b)$ است. بنابراین ممکن نیست برخی بلوک‌ها از نوع $(a)$ باشند و برخی بلوک‌ها از نوع $(b)$.\\ دو حالت باقی‌مانده‌است که یا تمام بلوک‌ها از نوع $(a)$ هستند، یا همه از نوع $(b)$ هستند. اما اگر تمام بلوک‌ها از نوع $(a)$ باشند، ترید زنجیری است، که با قضیه \ref{22.2.2} رد شده‌است. بنابراین ما تنها حالتی را در نظر می‌گیریم که تمام بلوک‌ها از نوع $(b)$ هستند. یکی از بلوک‌ها را در نظر بگیرید، مثلاً $G_1$ . هر رأس از $G_1$ در دقیقاً یک بلوک دیگر از $T_1$ واقع می‌شود، در حقیقت $V(G_1)$ اجتماعی از $-p$ مجموعه‌های مجزای\\ $V(G_1) \cap V(G_i)$ ، $(i=2,3,4,5)$ است. مجموعه رأس‌های هر بلوک $T_1$ اجتماعی از چهار $-p$ مجموعه مجزا از $V(G_i) \cap V(G_j)$ ، $i , j \in \lbrace 1,2,3,4,5 \rbrace) $ ، $(i \neq j$ است. دقیقاً ده تا از چنین مجموعه‌هایی وجود دارد؛ آن‌ها را $Q_1 , Q_2 ,Q_3 , \ldots Q_{10}$ می‌نامیم. هر کدام از آن‌ها دقیقاً در دو بلوک از $T_1$ واقع می‌شوند. متناظراً، بلوک‌های $T_2$ دارای ساختار مشابه هستند؛ در حقیقت ما قبلاً نشان دادیم که اگر $G_i$ از نوع $(b)$ باشد و $G_j$ از هر بلوک دیگر $T_1$ ، آنگاه $ Q = V (G_i ) \cap V (G_j ) = V (G'_k) \cap V (G'_l) $ برای یک $G'_k ,G'_l \in T_2 $ . بنابراین مجموعه رأس از هر بلوک $T_2$ نیز اجتماعی از چهار مجموعه $Q_i$ ، $(i \in \lbrace 1,2,3, \ldots 10 \rbrace)$ است. توجه داشته باشید که این مجموعه رأس‌ها لزوماً با بخش‌های بلوک‌ها مطابقت ندارد.\\ برای هر بلوک $G_i$ یا $G'_i$ یک بلوک موازی به ترتیب $F_i$ یا $F'_i$ می‌سازیم، که با $K_4$ یکریخت است. چهار رأس از بلوک موازی را با چهار مجموعه در $\lbrace Q_1 , Q_2 ,Q_3 , \ldots, Q_{10} \rbrace$ برچسب گذاری می‌کنیم که مجموعه رأس‌های بلوک اصلی را تشکیل می‌دهند. فرض کنید $U= \lbrace F_1,F_2,F_3,F_4,F_5 \rbrace$ ، $U'= \lbrace F'_1,F'_2,F'_3,F'_4,F'_5 \rbrace$.\\ حال اگر $Q_{\alpha}$ و $Q_{\beta}$ در یک بلوک $G_i$ از $T_1$ واقع شوند، آنگاه باید حداقل یک یال بین یک رأس از $Q_{\alpha}$ و یک رأس از $Q_{\beta}$ وجود داشته باشد( چون تمام $2p$ رأس در یک بخش $G_i$ نمی‌توانند واقع شوند). بنابراین $Q_{\alpha}$ و $Q_{\beta}$ باید با هم در یک بلوک از $T_2$ واقع شوند. بنابراین اگر یک یال $Q_{\alpha}Q_{\beta}$ در یک عضو $U$ واقع شود، باید در یک عضو $U'$ نیز واقع شود( و برعکس طبق تقارن).\\ هیچ یالی بیشتر از یک بار در $U$ یا $U'$ نمی‌تواند واقع شود، چون این بدان معنی است که یا دو بلوک از $T_1$ یا دو بلوک از $T_2$ دارای $2p$ رأس یا بیشتر، مشترک هستند. چون همه بلوک‌ها در $T_1$ از نوع $(b)$ هستند، مجموعه رأس‌های بلوک‌های $T_1$ از مجموعه رأس‌های بلوک‌های $T_2$ مجزا است. بنابراین $U$ و $U'$ متمایز هستند.\\ نتیجه می‌شود که $\lbrace U , U' \rbrace$ یک $K_4$ اشتاینر ترید مناسب از حجم $5$ است. اما می‌دانیم چنین تریدی وجود ندارد. بنابراین ما یک تناقض برای حالت آخر داریم. \end{proof} خلاصه نتایج برای طیف ترید گراف‌های چندبخشی کامل را در قضیه زیر می‌آوریم. \begin{theorem} فرض کنید $G$ یک گراف چند بخشی کامل باشد.\\ $(i)$ اگر $n$ بخش از اندازه یک وجود داشته باشد( پس $G$ یک گراف کامل $K_n$ است) آنگاه: $\rbrace$ فرد $X(K_n) = \lbrace t \vert\; 1 \leq t \leq 2n-3 \rbrace \cup \lbrace t \vert\; 2n-1 \leq t \leq 3n-4 , t $ . با دقیقاً این استثنا: $TS(K_2) = \lbrace 0 \rbrace$ و $15 \in TS(K_7)$. \\ $(ii)$ اگر تمام $n$ بخش اندازه یکسان $p$ ، $(p \geq 2)$ داشته‌باشند، آنگاه: \begin{center} \begin{tabular}{|c|c|c|} \hline طیف ترید &حجم ممنوع ترید &تعداد بخش‌ها \\ \hline$TS(G) = \lbrace 1,2,3,\ldots \rbrace $& $X(G) = \emptyset$& $1$\\ $TS(G) = \lbrace2,3,4,\ldots \rbrace $& $\lbrace 1 \rbrace $& $2$\\ $TS(G) = \lbrace 4,5,6,\ldots \rbrace $&$\lbrace 1,2,3 \rbrace $& $3$\\ $TS(G) = \lbrace 6,7,8,\ldots \rbrace $& $\lbrace 1,2,3,4,5 \rbrace $& $n \geq 4$\\ \hline \end{tabular} \end{center} $(iii)$ اگر تمام اندازه بخش‌های $a_i$ ، $(1 \leq i \leq n)$ ، یکسان نباشند، آنگاه $X(G) = \lbrace 1,2 \rbrace$ ، به جز $2 \in TS(G)$ در دو حالت زیر: $(a)$ $n=2$ ؛ $(b)$ $n \geq 3$ ، و برای یک $1 \leq i , j \leq n$ ، $2a_j = a_i +\sum_{k=1}^{n} a_k$. \end{theorem} \section{طیف ترید از گراف‌های ستاره‌ای } برای عدد صحیح $x \geq 0$ ، گراف $K_{1,x}$ یک $x$ ستاره گفته می‌شود. فرض می‌کنیم $[a_0 : a_1,a_2,a_3,\ldots ,a_x]$ یک کپی از $K_{1,x}$ را با مجموعه رأس $\lbrace a_i \vert\; 0 \leq i \leq x \rbrace$ و مجموعه یال $\lbrace a_0a_i \vert\; 1 \leq i \leq x \rbrace$ تعریف کند. رأس $a_0$ به عنوان رأس مرکزی تعریف شده‌است. در این بخش طیف $K_{1,x}$ ترید برای هر مقدار ممکن $x$ و هر بنیان ممکن را بدست می‌آوریم؛ که، مجموعه ای از سه تایی‌های $(x,s,v)$ است که برای آن یک $T_{K_{1,x}} (s,v)$ وجود دارد. در این‌جا ما مسأله طیف ترید را برای یک خانواده‌ی نامتناهی از گراف‌ها، حل می‌کنیم. نتایج در قضیه زیر خلاصه شده‌است. \begin{theorem}\label{s1.1} یک $T_{K_{1,x}}(s,v)$ وجود دارد اگر و فقط اگر $x\geq 2$ ، $v \geq x+2$ ، و $m_x (v) \leq s \leq M_x(v)$ ، که $m_x(v)$ و $M_x(v)$ به این صورت تعریف شده‌اند \begin{equation*} m_x(v)= \left\{ \begin{array}{ll} 3& v \leq 2x \text{و }\;x \geq 3\text{اگر }\\ \lceil \frac{2v}{2x+1}\rceil & \text{در غیر این صورت }\\ \end{array} \right. \end{equation*} \begin{equation*} M_x(v)= \left\{ \begin{array}{ll} 2(v-x)-1& v \leq 2x\;\text{اگر } \\ \lfloor\frac{v(v-1)}{2x}\rfloor &v \geq 2x+1\; \text{اگر } \\ \end{array} \right. \end{equation*} \end{theorem} ابتدا لزوم شرایط را ثابت می‌کنیم و سپس با ارائه ساختارهایی کفایت شرط‌ها را نشان می‌دهیم. \subsection{شرط‌های لازم} اگر $x \leq 1$ ، آنگاه $K_{1,x}$ یا یک رأس تنها است یا یک یال تنها، و بنابراین هیچ $-K_{1,x}$ ترید وجود ندارد. بنابراین از این‌جا به بعد فرض می‌کنیم که $x \geq 2$ است. این بخش را با یک کران ساده روی حجم ترید‌های ممکن شروع می‌کنیم. \begin{lemma}\label{s2.1} فرض کنید $x$ ، $s$ و $v$ اعداد صحیحی باشند، ‌که یک $T_{K_{1,x}}(s,v)$ وجود دارد. آنگاه\\ $\lceil \frac{2v}{2x+1}\rceil \leq s \leq \lfloor \frac{v(v-1)}{2x} \rfloor$. \end{lemma} \begin{proof} کران بالا روی $s$ از شمارش ساده تعداد یال‌ها بدست می‌آید، چون در هر نیمه از ترید $sx$ یال وجود دارد، و در $K_v$ ، $v(v-1)/2$ یال وجود دارد، پس $\frac{v(v-1)}{2} \leq sx$ و داریم $s \leq \lfloor \frac{v(v-1)}{2x} \rfloor$. فرض کنید $G$ گراف ساده روی $n$ رأس باشد که شامل یک رأس برشی است. در قضیه \ref{61.2} نشان داده شده‌است که شرط لازم برای وجود $T(s,v)$ این است که $s \geq 2v/(2n-1)$ . چون $-x$ ستاره شامل $x+1$ رأس است و به شرط اینکه $x \geq 2$ یک رأس برشی دارد(رأس مرکزی)، کران پایین روی $s$ از این نتیجه کلی بدست می‌آید. \end{proof} در حالت $v \leq 2x$ می‌توانیم این کران‌ها را بهبود دهیم. \begin{lemma}\label{s2.2} فرض کنید $x$ ، $s$ و $v$ اعداد صحیح باشند به طوری که یک $T_{K_{1,x}}(s,v)$ وجود دارد. اگر $v \leq 2x$ آنگاه $s \leq 2(v-x)-1$ است. \end{lemma} \begin{proof} طبق لم \ref{s2.1} ، داریم $s \leq v(v-1)/2x$ ، و با استفاده از فرض $v \leq 2x$ ؛ پس $s \leq v-1$. فرض کنید $\lbrace T_1 , T_2 \rbrace$ تریدی با گراف اساسی $H$ باشد. هر یال استفاده شده در ترید باید با رأس مرکزی حداقل یکی از بلوک‌های $T_1$ برخورد داشته باشد( و مشابهاً برای $T_2$ ). $s$ بلوک از $T_1$ وجود دارد، و بنابراین حداکثر $s$ رأس، مرکز یک بلوک یا بیشتر هستند. بنابراین، حداقل $v-s$ رأس وجود دارند که رأس مرکزی نیستند. هیچ یالی نمی‌تواند یک جفت از این رأس‌ها را به یکدیگر متصل کند، و بنابراین حداکثر $\binom{s}{2}+s(v-s)$ یال در $H$ وجود دارد. از طرفی چون $H$ گراف اساسی ترید است $sx$ یال دارد، بنابراین $sx \leq s(s-1)/2 +s(v-s)$ است. پس $s \leq 2(v-x)-1$. \end{proof} \begin{lemma}\label{s2.3} فرض کنید $x$ ، $s$ و $v$ اعداد صحیحی باشند به‌طوری‌که یک $T_{K_{1,x}}(s,v)$ وجود داشته باشد. اگر $x \geq 3$ و $v \leq 2x$ باشد، آنگاه $s \geq 3$ است. \end{lemma} \begin{proof} باید ثابت کنیم هیچ $T_{K_{1,x}}(2,v)$ با $x \geq 3$ و $v \leq 2x$ وجود ندارد؛ فرض می‌کنیم چنین تریدی وجود دارد و یک تناقض پیدا می‌کنیم. فرض کنید $\lbrace \lbrace A_1 , B_1 \rbrace , \lbrace A_2 , B_2 \rbrace \rbrace $ چنین تریدی باشد، و فرض کنید $a_1$ ، $b_1$ ، $a_2$ و $b_2$ به ترتیب رأس‌های مرکزی $A_1$ ، $B_1$ ، $A_2$ و $B_2$ باشند. رأس‌های $a_1$ و $b_1$ در گراف اساسی $H$ درجه‌ی $3$ یا بیشتر دارند، زیرا $x \geq 3$ است. (یاد آوری می‌کنیم که $H=A_1 \cup B_1=A_2 \cup B_2$ )، در حالی‌که تمام رأس‌های دیگر در $H$ درجه‌ی $2$ یا کمتر دارند. این موضوع برای $a_2$ و $b_2$ نیز درست است، بنابراین $\lbrace a_1 , b_1 \rbrace = \lbrace a_2 , b_2 \rbrace$ ؛ گوییم $a_1=a_2=a$ و $b_1=b_2=b$.\\ اگر $a=b$ ، این رأس مرکز هر دوی $A_1$ و $B_1$ است، که مجاور بودن آن با $2x$ رأس در $H$ را ایجاب می‌کند. چون $v \leq 2x$ این یک تناقض است، و اثبات تمام است. حالت $a \neq b$ باقی‌مانده‌است. غیر از یال $ab$ ، تمام یال‌های $H$ که با $a$ برخورد دارند، باید در هر دوی $A_1$ و $A_2$ واقع شوند، در حالی‌که تمام یال‌های $H$ که با $b$ برخورد دارند باید در هر دوی $B_1$ و $B_2$ واقع شوند. تنها یال $ab$ باقی می‌ماند. اگر $ab$ در $A_1$ واقع شود باید در $A_2$ نیز واقع شود، چون در غیر این صورت تعداد یال‌های $A_1$ متفاوت از $A_2$ خواهد بود( که تناقض است). مشابهاً، اگر $ab$ در $B_1$ واقع شود باید در $B_2$ نیز واقع شود، و اگر $ab$ نه در $A_1$ یا نه در $B_1$ واقع نشود آنگاه نمی‌تواند در $A_2$ یا $B_2$ یا هردوی آن‌ها واقع شود. بنابراین $A_1=A_2$ و $B_1=B_2$ ، که باز یک تناقض می‌دهد. \end{proof} در حقیقت برای $x \geq 3$ تنها $-K_{1,x}$ ترید از حجم $2$ یک $T_{K_{1,x}}(2;K_{1,2x})$ است، و هر دو بلوکش رأس مرکزی یکسان دارد( ساختار این ترید در لم \ref{s3.1} گفته خواهد شد) شرط لازم، برای کران پایین $v$ در نتیجه زیر بیان می‌شود. \begin{corollary}\label{sc2.1} فرض کنید $x$ ، $s$ و $v$ اعداد صحیحی باشند به‌طوری‌که یک $T_{K_{1,x}}(s,v)$ وجود دارد. آنگاه $v \geq x+2$ است. \end{corollary} \begin{proof} اگر $v \geq 2x+1$ آنگاه چون $x \geq 2$ است نتیجه فوراً بدست می‌آید. بنابراین فرض می‌کنیم $v \leq 2x$ است. اگر $x \geq 3$ باشد، آنگاه طبق لم‌های \ref{s2.2} و \ref{s2.3} داریم $3 \leq 2(v-x)-1$ ، و نتیجه بدست می‌آید. در نهایت، اگر $x=2$ باشد، آنگاه طبق لم \ref{s2.2} داریم $2 \leq s \leq 2(v-x)-1=2v-5$ . چون $v$ عدد صحیح است، نتیجه می‌شود که $v \geq 4$ ، و پس در این حالت نیز $v \geq x+2$ ، و نتیجه بدست می‌آید. \end{proof} \subsection{ساختار‌ها} در این قسمت با ساختار‌های مناسب کفایت قضیه \ref{s1.1} را ثابت می‌کنیم \begin{lemma}\label{s3.1} برای هر $x$ و $s$ که صدق می‌کند در $x \geq 2$ و $s \geq 2$ ، یک $T_{K_{1,x}}(s;K_{1,sx})$ وجود دارد. \end{lemma} \begin{proof} فرض کنید\\ \begin{flushleft} $V=\lbrace a_{\infty} \rbrace \cup \lbrace a_i \vert\; i \in \mathbb{Z}_{sx} \rbrace,$\\ $T_1=\lbrace[ a_{\infty} : a_{ix}, a_{ix+1}, a_{ix+2},\ldots , a_{ix+x−1}] \vert\; 0\leq i\leq s-1\rbrace,$\\ $T_2=\lbrace[ a_{\infty} : a_{ix+1}, a_{ix+2}, a_{ix+3},\ldots , a_{ix+x}] \vert \;0\leq i\leq s-1\rbrace,$\\ \end{flushleft} که اندیس‌های $a$ بر پایه $sx$ گرفته شده‌اند. آنگاه $\lbrace T_1 ,T_2 \rbrace$ یک $T_{K_{1,x}}(s;K_{1,sx})$ است، با مجموعه رأس $V$ و رأس‌های مستقل $ \lbrace a_i \vert \;i \in \mathbb{Z}_{sx} \rbrace$. \end{proof} حال ساختار اصلی برای حالت $s \leq v$ را ارائه می‌دهیم. \begin{lemma}\label{s3.2} اگر $x$ ، $v$ و $s$ در $x \geq 2$ و $\lceil max(3, v/x)\rceil \leq s \leq min(v, 2(v -x) -1)$ صدق کند، آنگاه یک $T_{K_{1,x}}(s,v)$ وجود دارد. \end{lemma} \begin{proof} فرض کنید $V =\lbrace a_i \vert \;i \in \mathbb{Z}_{s}\rbrace \cup \lbrace b_i \vert\; i\in \mathbb{Z }_{v-s }\rbrace$ است، و فرض کنید $\alpha= min(x-1, v-s)$ است. برای $i \in \mathbb{Z}_s $ ، تعریف کنید: \begin{flushleft} $K_{1,x}^i=[a_i : a_{i+1}, a_{i+2}, \ldots , a_{i+x-\alpha}, b_{i\alpha}, b_{i\alpha+1}, b_{i\alpha+2},\ldots , b_{i\alpha+\alpha-1}],$\\ $K_{1,x}^{i*}= [a_i : a_{i-1}, a_{i-2}, \ldots , a_{i-(x-\alpha)}, b_{i\alpha}, b_{i\alpha+1}, b_{i\alpha+2},\ldots , b_{i\alpha+\alpha-1}],$\\ \end{flushleft} که اندیس‌های $b$ بر پایه $v-s$ گرفته شده‌است. آنگاه $\lbrace \lbrace K_{1,x}^i \vert \;i \in \mathbb{Z}_{s}\rbrace , \lbrace K_{1,x}^{i*} \vert\; i \in \mathbb{Z}_{s} \rbrace \rbrace$ یک $T_{K_{1,x}} (s,v)$ است. توجه کنید که $x-\alpha = max(1,x-v+s)$ است. بنابراین بلوک‌های $K_{1,x}^i$ و $K_{1,x}^{i*}$ همیشه به ترتیب شامل یال‌های $a_ia_{i+1}$ و $a_ia_{i-1}$ هستند(اما نه بر عکس)، حال باید مطمئن ‌شویم که ترید مناسب است، یعنی $K_{1,x}^i\neq K_{1,x}^{i*}$ است. چون $3 \leq s \leq 2(v-x)-1$ ، داریم $1 \leq (s-1)/2$ و $x-v+s \leq (s-1)/2$ ، و بنابراین $x- \alpha \leq (s-1)/2$ است. بنابراین نتیجه می‌شود که هیچ یال $a_ia_j$ تکرار نمی‌شود. چون $\alpha \leq v-s$ است، هیچ رأس $b_j$ در هیچ بلوکی تکرار نمی‌شود. اگر $\alpha = v-s$ باشد، هر رأس از $\lbrace b_i \vert \;i \in\mathbb{Z}_{v-s} \rbrace$ در هر بلوک واقع می‌شود( در این حالت جمله $i\alpha$ در اندیس‌های $b$ می‌تواند با $0$ جایگزین شود). اگر $\alpha=x-1$ ، آنگاه با استفاده از شرط $v/ x \leq s$ داریم $\alpha=s(x-1) \geq v-s$ ، و بنابراین هر رأس از $\lbrace b_i \vert \;i \in\mathbb{Z}_{v-s} \rbrace$ در حداقل یک بلوک واقع می‌شود. \end{proof} \begin{corollary}\label{sc3.1} شرط‌های قضیه \ref{s1.1} برای $v \leq 2x$ کافی هستند. \end{corollary} \begin{proof} وقتی‌که $v \leq 2x$ باشد، $\lceil max(3,v/x)\rceil=3$ است و $min(v,2(v-x)-1)=2(v-x)-1$ است. پس از لم \ref{s3.2} نتیجه بدست می‌آید، به جز وقتی‌که $s=2$ است. در حالت $s=2$ طبق لم \ref{s2.3} داریم $x=2$ ؛ بنابراین طبق فرض $v \leq 2x=4$ و طبق نتیجه \ref{sc2.1} ، $v \geq 4$ است. نتیجه می‌شود که $v=4$ است؛ پس یک $T_{K_{1,2}}(2;4)$ مناسب به صورت زیر است\\ \begin{flushleft} $T_1=\lbrace [3:1,2] , [4:1,2] \rbrace,$\\ $T_2= \lbrace [1:3,4] , [2:3,4] \rbrace.$\\ \end{flushleft} \end{proof} \begin{corollary}\label{sc3.2} برای اعداد صحیح $x$ ، $v$ ، $s$ که صدق می‌کند در $x \geq 2$ ، $v \geq 2x+1$ ، و $\lceil v/x \rceil \leq s \leq v$ ، یک $T_{K_{1,x}}(s,v)$ وجود دارد؛ یعنی، شرط‌های قضیه \ref{s1.1} برای $v \geq 2x+1$ و $\lceil v/x \rceil \leq s \leq v$ کافی هستند. \end{corollary} \begin{proof} وقتی‌که $v \geq 2x+1$ باشد، $\lceil max(3,v/x)\rceil=\lceil v/x \rceil$ است و\\ $min(v,2(v-x)-1)=2(v-x)-1=v$ است. بنابراین از لم \ref{s3.2} نتیجه بدست می‌آید. \end{proof} پس تاکنون مسأله برای $v \leq 2x$ کامل شده‌است، اما برای $v \geq 2x+1$ هنوز به ترید‌هایی از حجم‌هایی که صدق کند در $v+1 \leq s \leq \lfloor v(v-1)/2x \rfloor$ و $\lceil 2v/(2x+1)\rceil \leq s \leq v/x$ نیاز داریم. حال یک ساختار پیچیده برای حالت $v \leq s$ ارائه می‌دهیم. \begin{lemma}\label{s3.3} فرض کنید $x$ ، $v$ و $s$ اعداد صحیحی باشند که در $x \geq 2$ ، $v \leq 4x-1$ و\\ $v \leq s \leq v(v-1)/2x$ صدق می‌کنند. آنگاه یک $T_{K_{1,x}}(s,v)$ وجود دارد. \end{lemma} \begin{proof} طبق فرض داریم \begin{align} v \leq s ,\label{s1}\\ s \leq \frac{v(v-1)}{2x} ,\label{s2}\\ v \leq 4x-1 ,\label{s3} \end{align} تعریف کنید $m=s-v$ و $n=2v-s$ ، پس \begin{equation} m+n=v \label{s4} \end{equation} و \begin{equation} 2m+n=s \label{s5} \end{equation} طبق \eqref{s2} و \eqref{s3} ، داریم $s \leq (4x-1)(v-1)/2x < 2(v-1)$ ، و بنابراین $n \geq 3$ است. طبق \eqref{s1} ، داریم $m \geq 0$. فرض کنید $M= \lbrace a_i \vert\; i \in \mathbb{Z}_m \rbrace$ ، $N= \lbrace b_i \vert\; i \in \mathbb{Z}_n \rbrace$ ، و $V=M \cup N$ . روی مجموعه رأس $V$ یک مجموعه از $m$ کپی از $K_{1,2x}$ و $n$ کپی از $K_{1,x}$ را می‌سازیم، به نام بلوک‌ها، که دو به دو یال مجزا هستند. می‌گوییم این‌ها $m+n$ بلوک از یک بسته‌بندی از گراف کامل روی $V$ است. بلوک‌ها را به ترتیب با $K_{1,2x}^i$ ، $(i \in \mathbb{Z}_m)$ و $K_{1,x}^j$ ، $(j \in \mathbb{Z}_n)$ برچسب گذاری می‌کنیم. فرض می‌کنیم $a_i$ رأس مرکزی $K_{1,2x}^i$ و $b_i$ رأس مرکزی $K_{1,x}^i$ است. بنابراین $K_{1,2x}$ بلوک‌ها روی رأس‌های $M$ مرکزدار هستند، در حالی که $K_{1,x}$ بلوک‌ها روی رأس‌های $N$ مرکزدار هستند. ابتدا $K_{1,2x}$ بلوک‌ها را درنظرمی‌گیریم. تا آن‌جا که ممکن است، بلوک‌ها را با رأس‌هایی از $M$ کامل می‌کنیم. $m$ کپی از $K_{1,2x}$ شامل یک اجتماعی از $2mx$ یال است، و $\binom{m}{2}$ یال در $M$ وجود دارد. بنابراین $m$ کپی از $K_{1,2x}$ باید شامل اجتماعی از حداقل $2mx-m(m-1)/2$ یال بین $M$ و $N$ باشد؛ بنابراین، به طور میانگین، هر $K_{1,2x}$ بلوک باید شامل حداقل $2x-(m-1)/2$ رأس از $N$ باشد. تعریف می‌کنیم $\alpha=2x-(m-1)/2$ . طبق \eqref{s2} و \eqref{s3} ، داریم \begin{flushleft} $m=s-v \leq (4x-1)(v-1)/2x-v < v-2 \leq 4x-3;$ \end{flushleft} نتیجه می‌شود که $\alpha$ مثبت است( بنابراین $K_{1,2x}$ بلوک‌ها نمی‌توانند کامل داخل یال‌ها و رأس‌های $M$ باشند). اگر $m$ فرد باشد، $\alpha$ یک عدد صحیح است. $K_{1,2x}$ بلوک‌ها را می‌سازیم به‌طوری‌که هر یک شامل دقیقاً $\alpha$ رأس از $N$ باشند. برای $ i \in \mathbb{Z}_m$ ، تعریف می‌کنیم \begin{flushleft} $K_{1,2x}^i=[a_i:a_{i+1},\ldots , a_{i+\frac{m-1}{2}}, b_{\alpha i}, b_{\alpha i+1},\ldots, b_{\alpha i+\alpha-1}],$ \end{flushleft} که اندیس‌های $b$ به پیمانه $n$ گرفته شده‌اند.\\ اگر $m$ زوج باشد، چون $\alpha$ عدد صحیح نیست، داریم $\lfloor \alpha \rfloor=2x-m/2$ و $\lceil\alpha \rceil=2x-(m-2)/2$ . برای $i \in \mathbb{Z}_m$ ، فرض می‌کنیم \begin{equation*} K_{1,2x}^i= \left\{ \begin{array}{ll} [a_i:a_{i+1},\ldots , a_{i+\frac{m}{2}}, b_{\lfloor\alpha\rfloor i}, b_{\lfloor\alpha\rfloor i+1},\ldots , b_{\lfloor \alpha \rfloor i+\lfloor\alpha\rfloor-1}] & \; 0 \leq i \leq \frac{m}{2} -1\text{اگر } \\ [a_i:a_{i+1},\ldots , a_{i+\frac{m}{2}-1}, b_{\lceil\alpha\rceil i-\frac{m}{2}}, b_{\lceil\alpha\rceil i - \frac{m}{2}+1},\ldots, b_{\lceil\alpha\rceil i-\frac{m}{2}+\lceil\alpha\rceil - 1}] & \; \frac{m}{2} \leq i \leq m -1 \text{اگر }\\ \end{array} \right. \end{equation*} که اندیس‌های $b$ به پیمانه $n$ گرفته شده‌اند. برای اطمینان از این‌که هیچ رأسی از $N$ در هیچ $K_{1,2x}$ بلوکی تکرار نشده باشد، باید بررسی کنیم که $\alpha \leq n$ است(وقتی‌که $m$ فرد یا $m$ زوج است). اگر $n \geq 2x$ باشد، به‌ آسانی می‌بینیم که این برقرار است، پس فرض می‌کنیم $n \leq 2x-1$ باشد، پس $x \geq (n+1)/2 > (n-1)/2$ است، و بنابراین \begin{equation} nx > \binom{n}{2}. \label{s6} \end{equation} با استفاده از \eqref{s5} و \eqref{s2} داریم \begin{equation} nx+2mx = sx \leq \binom{v}{2}. \label{s7} \end{equation} طبق \eqref{s4} ، $m+n=v$ ، و بنابراین با درنظرگرفتن مجموعه‌ای از جفت‌ها روی یک مجموعه $-v$ تایی داریم \begin{equation} \binom{v}{2}=\binom{m}{2}+\binom{n}{2}+mn. \label{s8} \end{equation} با ترکیب عبارات \eqref{s6} ، \eqref{s7} و \eqref{s8} ، داریم \begin{equation*} 2mx < \binom{m}{2}+mn. \end{equation*} دو طرف نامساوی بالا را می‌توانیم به $m$ تقسیم کنیم، چون $m$ غیر صفر است، پس $2x0 $ که غیر ممکن است. \end{proof} \begin{lemma}\label{2.7} اگر $ G $ ، گراف اساسی یک $ T(s,v) $ باشد و $ G $ دنباله درجات $ 6,6,6,4,\ldots ,4,4 $ داشته باشد آنگاه $ G $ یک مولفه با دنباله درجات $6,6,6,4,4,4,4,4,4 $ دارد و همه مولفه‌های بعدی پیکربندی پاک هستند. \end{lemma} \begin{proof} فرض کنید که $ \{T_1, T_2\} $ یک $ T(s,v) $ با گراف اساسی $G$ است که $ G $ دنباله درجات $ 4,4, \ldots ,4,6,6,6 $ را دارد. چون هر مولفه $ G $ در خودش یک ترید است، مولفه‌ای از $ G $ با دقیقاً یک رأس درجه $ 6 $ نمی‌تواند وجود داشته باشد (طبق نتیجه \ref{2.3} ). بنابراین سه رأس درجه $ 6 $ باید همگی در یک مولفه باشند. حال نشان می‌دهیم که این مولفه باید شامل دقیقاً $ 6 $ رأس درجه $ 4 $ نیز باشد. فرض کنید $ a_0 $ یک رأس از درجه $ 6 $ باشد و فرض کنید $ a_6,a_5, a_4,a_3,a_2 , a_1$ همسایه‌هایش باشند. حداقل $ 4 $ تا از این رأس‌ها درجه $ 4 $ دارند بدون کم شدن از کلیت می‌توانیم فرض کنیم که \[a_0a_1a_2, a_0a_3a_4 , a_0a_5a_6 \in T_1\] و \[a_0a_2a_3, a_0a_4a_5 , a_0a_6a_1 \in T_2.\] همچنین، بدون کم شدن از کلیت می‌توانیم فرض کنیم که دقیقاً یکی از موارد زیر درست است:\\ (1) $ a_4,a_3,a_2,a_1 $ درجه $ 4 $ دارند؛\\ (2) $ a_5,a_3,a_2,a_1 $ درجه $ 4 $ دارند؛\\ (3) $ a_5,a_4,a_2,a_1 $ درجه $ 4 $ دارند؛\\ هربار یکی از سه حالت بالا را در نظر می‌گیریم.\\ (1) رأس سوم از مثلث در $ T_1 $ که شامل یال $ a_2a_3 $ است نمی‌تواند $ a_0, a_1 $ یا $ a_4 $ باشد چون آن‌ها قبلاً در مثلثی از $ T_1 $ با $ a_2 $ یا $ a_3 $ واقع شده‌اند. رأس سوم نمی‌تواند $ a_5 $ باشد چون $ a_3 $ درجه $ 4 $ دارد و نمی‌توانیم داشته باشیم $ a_3a_4a_5 \in T_2 $ (زیرا قبلاً داشتیم که $a_0a_4a_5 \in T_2$ ). به طور مشابه، رأس سوم نمی‌تواند $ a_6 $ باشد چون $ a_2 $ درجه $ 4 $ دارد و نمی‌توانیم داشته باشیم $ a_2a_1a_6 \in T_2 $ (زیرا قبلاً داشتیم که $a_0a_1a_6 \in T_2$ ). بنابراین رأس سوم باید یک رأس جدید $ a_7$ باشد؛ که $ a_2a_3a_7 \in T_1 $ . حال، چون $ a_2 $ درجه $ 4 $ دارد، $ a_1a_2a_7 \in T_2 $ و چون $ a_3 $ درجه $ 4 $ دارد، $ a_3a_4a_7 \in T_2 $ . همچنین، چون $ a_4 $ درجه $ 4 $ دارد، $ a_4a_5a_7 \in T_1 $ و چون $ a_1 $ درجه $ 4 $ دارد، $ a_1a_6a_7 \in T_1 $ . بنابراین $ a_7$ درجه $ 6$ دارد و پس حداقل یکی از $ a_5 $ و $ a_6 $ درجه $ 4 $ دارند. اگر هر دو $ a_5 $ و $ a_6 $ درجه $ 4 $ داشته‌باشند آنگاه مثلث‌های داده شده بالا یک مولفه کامل $ (T(6,8)) $ تعریف می‌کنند، اما این غیر ممکن است زیرا همه رأس‌ها از درجه $ 6 $ باید در یک مولفه باشند(اما در این مولفه فقط $ a_0 $ درجه $ 6 $ دارد ) . از سوی دیگر، اگر فقط یکی از آن‌ها درجه $ 6 $ داشته باشد آنگاه این رأس باید در دقیقاً یک مثلث در هر $ T_1 $ و $ T_2 $ واقع شود. اما آنگاه $ \vert T_1 \cap T_2\vert >0 $ که غیر ممکن است. (2) رأس سوم از مثلث در $ T_1 $ که شامل یال $ a_2a_3 $ است نمی‌تواند $ a_0, a_1 $ یا $ a_4 $ باشد چون آن‌ها قبلاً در مثلثی از $ T_1 $ با $ a_2 $ یا $ a_3 $ واقع شده‌اند. رأس سوم نمی‌تواند $ a_5 $ باشد چون $ a_5 $ درجه بزرگتر از $ 4 $ خواهد داشت. رأس سوم نمی‌تواند $ a_6 $ باشد چون $ a_2 $ درجه $ 4 $ دارد و نمی‌توانیم داشته باشیم $ a_1a_2a_6 \in T_2.$ بنابراین رأس سوم باید یک رأس جدید $ a_7$ باشد؛ که $ a_2a_3a_7 \in T_1 $ . حال، چون $ a_2 $ درجه $ 4 $ دارد، $ a_1a_2a_7 \in T_2 $ و چون $ a_3 $ درجه $ 4 $ دارد، $ a_3a_4a_7 \in T_2 $ . بنابراین، چون $ a_1 $ درجه $ 4 $ دارد، $ a_1a_6a_7 \in T_1 $ .این باعث می‌شود که $ a_7 $ رأسی از درجه $ 6 $ باشد چون قبلاً پنج همسایه ( $ a_1,a_2,a_3,a_4, a_6 $ ) در $ G $ داشته‌است. اگر ششمین همسایه‌اش $ a_5 $ باشد آنگاه این باعث می‌شود که $ a_4a_5a_7 \in T_1 $ و $ a_5a_6a_7 \in T_2 $. اگر هردو $ a_4 $ و $ a_6 $ درجه $ 4 $ داشته‌باشند آنگاه مثلث‌های داده شده تاکنون یک مولفه کامل $ (T(6,8)) $ تعریف می‌کند اما این غیر ممکن است زیرا همه رأس‌ها از درجه $ 6 $ باید در یک مولفه باشند. از سوی دیگر، اگر فقط یکی از آن‌ها درجه $ 6 $ داشته باشد آنگاه این رأس باید در دقیقاً یک مثلث در هر $ T_1 $ و $ T_2 $ واقع شود. اما آنگاه $ \vert T_1 \cap T_2\vert >0 $ که غیر ممکن است. بنابراین ششمین همسایه از $ a_7 $ باید یک رأس جدید $ a_8 $ باشد و باید $ a_4a_7a_8 \in T_1 $ و $ a_6a_7a_8 \in T_2 $ . اما این باعث می‌شود هر دو $ a_4 $ و $ a_6 $ درجه بزرگتر از $ 4 $ داشته‌باشند که غیر ممکن است (چون قبلاً داشتیم $ a_0 $ و $ a_7 $ با درجه $ 6 $ هستند). (3) رأس سوم از مثلث در $ T_1 $ که شامل یال $ a_2a_3 $ است نمی‌تواند $ a_0, a_1 $ یا $ a_4 $ باشد چون آن‌ها قبلاً در مثلثی از $ T_1 $ با $ a_2 $ یا $ a_3 $ واقع شده‌اند. رأس سوم نمی‌تواند $ a_5 $ باشد چون $ a_5 $ درجه بزرگتر از $ 4 $ خواهد داشت. رأس سوم نمی‌تواند $ a_6 $ باشد چون $ a_2 $ درجه $ 4 $ دارد و نمی‌توانیم داشته باشیم $ a_1a_2a_6 \in T_2 $ . بنابراین رأس سوم باید یک رأس جدید $ a_7$ باشد؛ که $ a_2a_3a_7 \in T_1 $ . حال، چون $ a_2 $ درجه $ 4 $ دارد، $ a_1a_2a_7 \in T_2 $ و چون $ a_1 $ درجه $ 4 $ دارد، $ a_1a_6a_7 \in T_1 $ رأس سوم از مثلثی در $ T_1 $ که شامل یال $ a_4a_5 $ است باید $ a_7 $ یا یک رأس جدید $ a_8 $ باشد. اگر $ a_4a_5a_7 \in T_1 $ آنگاه مجبوریم داشته باشیم $ a_3a_4a_7 \in T_2 $ و $ a_5a_6a_7 \in T_2 $ ، اما این به ما یک مولفه کامل می‌دهد که در دو حالت قبل دیدیم که غیر ممکن است. بنابراین $ a_4a_5a_8 \in T_1 $ (چون $ a_4 $ و $ a_5 $ درجه $ 4 $ دارند)، که باعث می‌شود داشته باشیم $ a_3a_4a_8 \in T_2 $ و $ a_5a_6a_8 \in T_2 $ . حال، هر دو $ a_3 $ و $ a_6 $ درجه بزرگ‌تر از $ 4 $ دارند و پس $ a_0,a_3 $ و $ a_6 $ باید رأس‌هایی از درجه $ 6 $ باشند. بنابراین، $ a_7 $ و $ a_8 $ درجه $ 4 $ دارند، پس $ a_3a_6a_7 \in T_2 $ و $ a_3a_6a_8 \in T_1$ است. این یک مولفه کامل تعریف می‌کند: یک $ T(7,9) $ دارای دنباله درجات $ 4,4,4,4,4,4,6,6,6 $. \end{proof} \begin{corollary}\label{2.8} اگر $ G $ ، گراف اساسی یک ترید باشد و $ G $ دنباله درجات $6,6,6,\ldots , 4,4 $ را داشته باشد آنگاه $ G $ باید $ 6x+9 $ رأس برای یک عدد صحیح نامنفی $ x $ داشته باشد. \end{corollary} \begin{proof} طبق لم \ref{2.7} ، $ G $ باید یک مولفه با $ 9 $ رأس داشته باشد و تمام مولفه‌های دیگر با $ 6 $ رأس باشند. \end{proof} \begin{corollary}\label{2.9} اگر $ v\equiv 0 (\textsc{ mod} \; 6) $ ،آنگاه هیچ $ T( \frac{2v}{3}+1, v) $ وجود ندارد. \end{corollary} \begin{proof} فرض کنید $ G $ ، گراف اساسی یک ترید باشد و فرض کنید $ v=6x $ باشد؛ پس $\frac{2v}{3} +1=4x+1 $ است. آنگاه $ \vert E(G) \vert =12x+3 $ و $ G $ باید دارای دنباله درجاتی باشد که مجموع آن $ 24x+6 $ است. اما این غیر ممکن است چون:\\ (1) $ 10,4, \ldots, 4,4 $ طبق نتیجه \ref{2.3} رد شده‌است؛\\ (2) $ 8,6,4, \ldots,4,4 $ طبق لم \ref{2.6} رد شده‌است؛\\ (3) $ 6,6,4, \ldots,4,4 $ طبق نتیجه \ref{2.8} رد شده‌است. \end{proof} \begin{lemma}\label{2.100} هیچ $ T(7,8) $ وجود ندارد. \end{lemma} \begin{figure}[b] \centering \includegraphics[width=4.5cm]{c3,1.jpg} \caption{} \label{c3,1} \end{figure} \begin{proof} فرض کنید $ G $ ، گراف اساسی یک $ T(7,8) $ باشد و $ G' $ را مکمل $ G $ درنظربگیرید. اگر $ G' $ شامل یک مثلث باشد، آنگاه ترید با این مثلث اضافه شده به $ T_1 $ و $ T_2 $ یک جفت بسته‌بندی ماکسیمم از مرتبه $ 8 $ که اشتراک $ 1 $ دارند خواهد بود. اما می‌دانیم هیچ چنین ماکسیم بسته بندی وجود ندارد، و پس $ G' $ بدون مثلث است. حال به آسانی دیده می‌شود که $ G $ باید دنباله درجات $6,6,6,6,6 ,4,4,4 $ را داشته باشد و پس $ G' $ دنباله درجات $ 3,3,3,1,1,1,1,1 $ را دارد. به آسانی بررسی می‌شود که تنها گراف بدون مثلث با این دنباله درجات آن است که در شکل \ref{c3,1} نشان داده شده‌است. بنابراین $ G $ باید همانطوری باشد که در شکل \ref{c3,2} نشان داده شده‌است. \begin{figure}[h] \centering \includegraphics[width=6cm]{c3,2.jpg} \caption{}\label{c3,2} \end{figure} اما دراین‌صورت فقط یک مثلث شامل یال $ e $ وجود دارد، که غیر ممکن است. \end{proof} برای هر $ v \geq 6 $ نتایج به دست آمده تا کنون، یک مجموعه $ P(v) $ از مقادیری از $ s $ را می‌دهد که برای آن ممکن است یک $ T(s,v) $ وجود داشته باشد. این نتایج را در جدول \ref{T32.1} خلاصه می‌کنیم. \begin{table}[h] \begin{center} \begin{tabular}{|c|c|} \hline $P(v) $ & $ v $ \\ \hline $\emptyset$ & $ v\leq 5 $\\ $ \lbrace 6,8\rbrace $ & $ v=8 $\\ $ \lbrace \frac{2v}{3} , \frac{2v}{3}+2, \frac{2v}{3}+3 , \ldots, \frac{v(v-2)}{6} \rbrace $ & $ v\geq 6 , v\equiv 0(\textsc{ mod} \; 6) $\\ $ \lbrace \frac{2v+4}{3} , \frac{2v+4}{3}+1, \ldots, \frac{v(v-1)}{6} \rbrace $& $ v\geq 7 , v\equiv 1(\textsc{ mod} \; 6) $\\ $ \lbrace \frac{2v+2}{3} , \frac{2v+2}{3}+1, \ldots, \frac{v(v-2)}{6} \rbrace $& $ v\geq 14 , v\equiv 2(\textsc{ mod} \; 6) $\\ $ \lbrace \frac{2v+3}{3} , \frac{2v+3}{3}+1, \ldots, \frac{v(v-1)}{6} \rbrace $& $ v\geq 9 , v\equiv 3(\textsc{ mod} \; 6) $\\ $ \lbrace \frac{2v+4}{3} , \frac{2v+4}{3}+1, \ldots, \frac{v^2-2v-2}{6} \rbrace $& $ v\geq10 , v\equiv 4 (\textsc{ mod} \; 6) $\\ $ \lbrace \frac{2v+2}{3} , \frac{2v+2}{3}+1, \ldots, \frac{v^2-v-8}{6} \rbrace $& $ v\geq 11 , v\equiv 5(\textsc{ mod} \; 6) $\\ \hline \end{tabular} \caption{} \label{T32.1} \end{center} \end{table} فرض کنید $ E(v) $ مجموعه‌ای از مقادیر $ s $ است، که یک $ T(s,v) $ وجود دارد. در ادامه ثابت می‌کنیم که برای هر $ E(v)=P(v), v\geq 6 $. \subsection{نتایج وجودی} \begin{lemma}\label{3.1} فرض کنید $ (G,S_1) $ و $ (G,S_2) $ یک جفت $ PTS(v) $ باشند که :\\ (1) $ \vert S_1\vert =\vert S_2 \vert=b $;\\ (2) $ \vert S_1 \cap S_2 \vert =I $;\\ (3) بزرگترین درجه مکمل $ G' $ از $ G $، $ d $ است.\\ آنگاه، اگر $ v-d-1>2I $، یک $ T(b-I, v) $ وجود دارد. \end{lemma} \begin{proof} چون $ v-d-1>2I $، هر رأس در $ S_1\setminus (S_1 \cap S_2) $ (و در $ S_2\setminus (S_1 \cap S_2) $ ) قرار می‌گیرد. بنابراین $ \{S_1\setminus (S_1 \cap S_2), S_2 \setminus (S_1 \cap S_2) \} $ یک $ T(b-I, v) $ روی گراف $G\setminus (S_1 \cap S_2)$ است. \end{proof} توجه کنید که اگر در لم \ref{3.1} ، $ I > 0 $ باشد آنگاه $ G $ یک مجموعه از $ 3 $ رأس مستقل دارد؛ رأس‌هایی از هر مثلث را در $ S_1 \cap S_2 $ درنظربگیرید.\\ بااستفاده از حل مسأله‌ی اشتراک برای ماکسیمم بسته بندی و نتایج بالا $ T(s,v) $ ها را برای $ s $ و $ v $ داده شده در جدول \ref{T33.2} بدست می‌آوریم. برای راحتی، حل مسأله اشتراک ماکسیمم بسته بندی سه‌گانه در جدول \ref{T33.1} داده شده‌است.( توجه کنید برای $ v \equiv 1,3 ( \textsc{ mod} \; 6) $ ، $ d = 0 $ ؛ برای $ v \equiv 0,2 ( \textsc{ mod} \; 6) $ ، $ d = 1 $ ؛ برای $ v \equiv 4 ( \textsc{ mod} \; 6) $ ، $ d = 3 $ ؛ و برای $ v \equiv 5 ( \textsc{ mod} \; 6) $ ، $ d = 2 $ است.)\\ \begin{table}[h] \begin{center} \begin{tabular}{|c|c|} \hline اندازه‌ی اشتراک ممکن & مرتبه‌ی ماکسیمم بسته بندی \\ \hline $ I \in \lbrace 0,4 \rbrace$ & $ v = 6 $\\ $ I \in \lbrace 0,1,3,7 \rbrace$ & $ v = 7 $\\ $ I \in \lbrace 0,2,8 \rbrace$ & $ v = 8 $\\ $ I \in \lbrace 0,1,2,3,4,6,12 \rbrace$ & $ v = 9 $\\ $ I \in \lbrace 0,1,2 ,\ldots,v(v-2)/6 = q \rbrace \setminus \lbrace q-1,q-2,q-3,q-5 \rbrace$ & $ v \equiv 0,2 (\;\textsc{ mod} \; 6) v \geq 12 $\\ $ I \in \lbrace0,1,2 ,\ldots,v(v-1)/6 = q \rbrace \setminus \lbrace q-1,q-2,q-3,q-5 \rbrace$ & $ v \equiv 1,3 (\;\textsc{ mod} \; 6) v \geq 13$\\ $ I \in \lbrace0,1,2 ,\ldots, (v^2-2v-2)/6 = q \rbrace \setminus \lbrace q-1,q-2,q-3,q-5 \rbrace$ & $ v \equiv 4 (\;\textsc{ mod} \; 6) v \geq 10$\\ $ I \in \lbrace 0,1,2,\ldots,(v^2-2v-8)/6 = q \rbrace \setminus \lbrace q-1,q-2,q-3,q-5 \rbrace$ & $ v \equiv 5 (\;\textsc{ mod} \; 6) v \geq 11$\\ \hline \end{tabular} \caption{حل مسأله اشتراک ماکسیمم بسته بندی سه‌گانه} \label{T33.1} \end{center} \end{table} \begin{corollary}\label{3.2} برای هر $ v $ و هر $ s $ نظیر در جدول \ref{T33.2} یک $ T(s,v) $ وجود دارد. \begin{table}[h] \begin{center} \begin{tabular}{|c|c|} \hline $s $ & $v $ \\ \hline$ s=4 $ & $ v=6 $\\ $s=6,7$ & $ v=7 $\\ $ s=6,8 $ & $ v=8 $\\ $6x^2 -5x+2 \leq s \leq 6x^2-2x $&$v=6x \geq 12$\\ $6x^2 -2x+1 \leq s \leq 6x^2+x $& $v=6x+1\geq 13 $\\ $6x^2 -x+1 \leq s \leq 6x^2+2x $& $ v=6x+2\geq 14 $\\ $6x^2 +2x+1 \leq s \leq 6x^2+5x+1 $& $ v=6x+3\geq 9 $\\ $6x^2 +3x+2 \leq s \leq 6x^2+6x+1 $& $ v=6x+4\geq 10 $\\ $6x^2 +6x+2 \leq s \leq 6x^2+9x+2 $&$ v=6x+5\geq 11 $\\ \hline \end{tabular} \caption{} \label{T33.2} \end{center} \end{table} \end{corollary} \begin{lemma}\label{3.3} فرض کنید گراف $ G_1 $ یک مجموعه از $ m $ رأس مستقل دارد و $ G_1 $ ، گراف اساسی یک $ T(s_1,v_1) $ است. اگر یک $ T(s_2,v_2) $ وجود داشته باشد، آنگاه یک $ T(s_1+s_2, v_1+v_2-n) $ برای $ n=0,1, \ldots,min(m,v_2) $ وجود دارد. \end{lemma} \begin{proof} فرض کنید $ \{T_1,T_2\}$ یک $ T(s_1,v_1) $ روی گراف $G_1$ باشد( $ G_1 $ یک مجموعه از $ m $ رأس مستقل دارد) و فرض کنید $ \{T'_1,T'_2\} $ یک $ T(s_2,v_2) $ روی گراف $G_2$ باشد. $ n $ رأس از $ G_2 $ را با $ n $ رأس مستقل $ G_1 $ یکسان درنظرمی‌گیریم. آنگاه $ \{T_1 \cup T'_1 , T_2\cup T'_2\} $ روی گراف $G_1\cup G_2$ ترید مطلوب است. \end{proof} لم \ref{3.3} برای ساختن ترید‌های جدید وقتی‌که ما وجود ترید‌هایی با تعداد رأس‌های مستقل زیاد را داریم، مفید است، مانند ترید‌های بدست آمده از حل مسأله‌ی اشتراک برای سیستم‌های سه‌گانه تقسیم‌پذیر گروهی. با استفاده از حل این مسأله در \cite{cDD} ، اگر دو سیستم سه‌گانه تقسیم پذیر گروهی با $g$ از اندازه $t$ داشته باشیم، اگر $\frac{g^2t(t-1)}{2} \equiv 0 (\textsc{mod}\; 3)$ و $g(t-1) \equiv 0 (\textsc{mod}\; 2)$ باشد آنگاه\\ $I \in \{0, \ldots, b\} \setminus \{b-1,b-2,b-3,b-5\}$ است، که $b=\frac{g^2t(t-1)}{6} $ است. در این‌جا تنها نیاز داریم که از سیستم‌های سه‌گانه‌ی تقسیم‌پذیر گروهی با سه گروه استفاده کنیم(پس شرایط بالا برای هر اندازه گروه $x$ برقرار است). با استفاده از حل مسأله‌ی اشتراک سیستم‌های سه‌گانه‌ی تقسیم‌پذیر با سه گروه و لم \ref{3.1} ، نتیجه‌ی زیر را بدست می‌آوریم. \begin{corollary}\label{3.4} زیرگراف $ G $ از گراف کامل سه بخشی $ K_{x,x,x} $ که یک $ T(s,3x) $ می‌دهد برای $ s $ و $ x $ داده شده در جدول \ref{T33.3} وجود دارد. \begin{table} \begin{center} \begin{tabular}{|c|c|} \hline $s $ & $x $ \\ \hline$4 $ & $ x=2 $\\ $9$ & $ x=3 $\\ $ x^2-x+1,x^2-x+2, \ldots x^2 $ & $ x\geq 4 $\\ \hline \end{tabular} \caption{}\label{T33.3} \end{center} \end{table} \end{corollary} \begin{lemma}\label{3.5} فرض کنید $ (G,S_1) $ و $ (G,S_2) $ یک جفت سیستم سه‌گانه تقسیم‌پذیر گروهی با سه گروه از اندازه $x$، $(v=3x)$ ، که $ \vert S_1 \vert =\vert S_2 \vert=x^2 $ و $\vert S_1 \cap S_2 \vert=I$ باشند.\\ (1) اگر $T(s_2,x) , T(s_1,x)$ و $T(s_3, x)$ وجود داشته‌باشند $T(s_1+s_2+s_3+x^2-I,3x) $ وجود دارد.\\ (2) اگر $T(s_1, x+1) , T(s_2,y)$ و $T(s_3,z)$ وجود داشته‌باشند، که $y$ و $z$ یا $x$ یا $x+1$ هستند،\\ $T(s_1+s_2+s_3+x^2-I,3x+1)$ وجود دارد.\\ (3) اگر $T(s_1, x+2) , T(s_2,y)$ و $T(s_3,z)$ وجود داشته‌باشند، که $y$ و $z$ یا $x+1,x$ یا $x+2$ هستند و حداکثر یکی از ترید‌ها از مرتبه $x+2$ هیچ زوج رأس مستقل ندارد، $T(s_1+s_2+s_3+x^2-I, 3x+2) $ وجود دارد. \end{lemma} \begin{proof} می‌توانیم فرض کنیم (طبق لم \ref{3.1} ) که یک $T(x^2-I,3x)$ وجود دارد که شامل سه مجموعه مجزا از $x$ رأس مستقل است(چون $G$ گراف $K_{x,x,x}$ است). شرط $v-d-I> 2I$ در لم \ref{3.1} تنها شرط لازم است که مطمئن شویم هیچ رأس تنهایی وجود ندارد. این‌جا ما سه تایی اضافه از ترید‌هایی از حجم $s_2, s_1$ و $s_3$ را قرار می‌دهیم، رأس تنها وجود نخواهد داشت و نیاز نداریم این شرط را بررسی کنیم. بنابراین نتیجه از لم \ref{3.3} بدست می‌آید.(سه بار به کار ببرید) \end{proof} \begin{lemma}\label{3.6} یک $T(x,x+2)$ برای همه اعداد صحیح زوج $x\geq 4$ وجود دارد \end{lemma} \begin{proof} فرض کنید $G$ گرافی با مجموعه رأس‌های \[V(G) = \lbrace \infty_1 , \infty_2 \rbrace \cup \lbrace 1,2,\ldots, x \rbrace \] و مجموعه یال \[E(G) = \lbrace \infty_1 1 , \infty_1 2, \ldots, \infty_1 x, \infty_2 1 ,\infty_2 2 , \ldots , \infty_2 x , 12 , 23 , 34 , \ldots , (x-1)x, x1 \rbrace\] است. همچنین، فرض کنید \[T_1 = \lbrace \infty_1 12 , \infty_1 34, \ldots , \infty_1 (x-1)x , \infty_2 23 ,\infty_2 45, \ldots , \infty_2 x1 \rbrace \] و \[ T_2 = \lbrace \infty_1 23 ,\infty_1 45, \ldots , \infty_1 x1 , \infty_2 12, \infty_234, \ldots , \infty_(x-1) x \rbrace. \] آنگاه $ \{T_1, T_2\} $ یک $T(x , x+2)$ روی گراف $G$ است. \end{proof} \begin{lemma}\label{3.7} برای $E(v)=P(v), v\leq 15 $. \end{lemma} \begin{proof} برای $v\leq 5$ چیزی برای اثبات وجود ندارد و برای $8$ و $ v=6,7$ با استفاده از نتیجه \ref{3.2} بدست می‌آید. برای نشان دادن $E(9) = P(9)$ ، دوباره طبق نتیجه \ref{3.2} ، تنها یک $T(7,9)$ و یک $T(8,9)$ نیاز داریم؛ که هر دو در پیوست \eqref{C3} داده شده‌است. مقادیر باقی‌مانده‌ی $v$ ، $(10\leq v \leq 15)$ را هر بار به‌طور جداگانه درنظرمی‌گیریم.\\ \underline{$ v=10$.} طبق نتیجه \ref{3.2} ، تنها نیاز داریم نشان دهیم که $8,9, 10 \in E(10)$. یک $T(8,10)$ طبق لم \ref{3.6} وجود دارد و $T(9, 10)$ و $T(10,10)$ در پیوست \eqref{C3} آمده‌است.\\ \underline{$v=11$.} طبق نتیجه \ref{3.2} ، تنها نیاز داریم نشان دهیم که $8,9, \ldots ,13 \in E(11)$. چون $T(4,6)$ یک جفت رأس مستقل دارد، طبق لم \ref{3.3} می‌توانیم از $T(4,6)$ همراه با $T(6,7)$ و $T(7,7)$ برای ساختن $T(8,11) , T(10,11)$ و $T(11,11)$ استفاده کنیم. ترید‌های باقی‌مانده $T(9,11) , T(12,11)$ و $T(13,11)$ در پیوست \eqref{C3} آمده‌است.\\ \underline{$ v=12$.} طبق نتیجه \ref{3.2} تنها نیاز داریم که نشان دهیم $8,10,11, \ldots ,15 \in E(12)$. چون $T(4,6)$ یک جفت رأس مستقل دارد، طبق لم \ref{3.3} می‌توانیم از $T(4,6)$ به همراه $T(6,7)،$ $T(7,7)$ و $T(8,8)$ برای ساختن $T(8,12) , T(10,12), T(11,12)$ و $T(12,12)$ استفاده کنیم. همچنین، با لم \ref{3.1} یک $T(9,9) , T(10,9)$ و $T(11,9)$ هر یک با یک مجموعه از سه رأس مستقل وجود دارد. بنابراین طبق لم \ref{3.3} می‌توانیم از آن‌ها به همراه $T(4,6)$ برای ساختن $T(13,12), T(14,12)$ و $T(15,12)$ استفاده کنیم.\\ \underline{$v=13$.} طبق نتیجه \ref{3.2} ، تنها نیاز داریم نشان دهیم که $10,11, \ldots ,20 \in E(13)$. این‌جا می‌توانیم از $T(4,6)$ به همراه $T(6,8),T(7,9), T(8,9), T(9,9),\ldots ,T(12,9)$ برای ساختن\\ $T(10,13) , T(11,13),\ldots , T(16,13)$ استفاده کنیم. چون $ T(10,9) $ و $T(11,9)$ هر یک با یک مجموعه از سه رأس مستقل وجود دارد، می‌توانیم از آن‌ها به همراه $T(7,7)$ برای ساختن $T(17,13)$ و $T(18,13)$ استفاده کنیم. ترید‌های باقی‌مانده $T(19,13)$ و $T(20,13)$ در پیوست \eqref{C3} آمده‌است.\\ \underline{$ v=14 $.} طبق نتیجه \ref{3.2} ، تنها نیاز داریم نشان دهیم که $10,11, \ldots ,22 \in E(14)$. این‌جا می‌توانیم از $T(4,6)$ به همراه $T(6,8),T(7,9), T(8,9), T(9,9),\ldots ,T(12,9),T(13,10)$ برای ساختن $T(10,14) , T(11,14),\ldots , T(17,14)$ استفاده کنیم.\\ برای ساختن $T(18,14) , T(19,14),\ldots , T(22,14)$ ابتدا از ترید‌های داده شده با بکار بردن لم \ref{3.1} برای جفت‌هایی از سیستم سه‌گانه تقسیم‌پذیر گروهی با $3$ گروه از اندازه $4$ و با $2,1$ و $0$ سه تایی مشترک استفاده می‌کنیم. این به ما $T(14,12), T(15,12)$ و $T(16,12)$ هر کدام با یک مجموعه از $4$ رأس مستقل را می‌دهد. سپس می‌توانیم یک $T(4,6)$ همراه با هر یک از آن ترید‌هابرای ساختن $T(18,14) , T(19,14)$ و $T(20, 14)$ استفاده کنیم. برای ساختن $T(21,14)$ از یک $T(13,12)$ شروع می‌کنیم که شامل دو مجموعه مجزا از $4$ رأس مستقل است؛ این ترید می‌تواند ساخته شود از یک جفت از سیستم سه‌گانه تقسیم‌پذیر گروهی با $3$ گروه از اندازه $4$ دارای $3$ سه تایی مشترک طبق لم \ref{3.1} . با استفاده از این ترید به همراه یک $T(4,6)$ می‌توانیم یک $T(17,14)$ بسازیم که شامل یک مجموعه از $6$ رأس مستقل است. این کار را با اطمینان از این که دو رأس از $T(4,6)$ با رأس‌های مستقل $T(13,12)$ یکی نیستند، امکان دارد. سپس این ترید می‌تواند با $T(4,6)$ دیگری برای ساختن $T(21,14)$ استفاده شود. یک $T(22,14)$ می‌تواند ساخته شود در یک روش مشابه با شروع از یک $T(14,12)$ که شامل دو مجموعه مجزا از $4$ رأس مستقل است.\\ \underline{$ v=15 $.} طبق نتیجه \ref{3.2} ، تنها نیاز داریم نشان دهیم که $11,12, \ldots ,28 \in E(15)$. این‌جا می‌توانیم از یک $T(4,6)$ به همراه تریدهای $T(7,9), T(8,11), T(9,11),\ldots ,T(17,11)$ برای ساختن\\ $T(11,15) , T(12,15),\ldots , T(21,15)$ استفاده کنیم. ترید‌های $T(22,15),T(23,15), T(24,15)$ و $T(25,15)$ طبق نتیجه \ref{3.4} وجود دارند.\\ می‌توانیم $T(26,15), T(27,15)$ و $T(28,15)$ با استفاده از لم \ref{3.2} با $s_1=s_2=s_3=4$ ، $ x+2=y=z=6$ و به ترتیب $0$ و $I=2,1$ بسازیم. \end{proof} \begin{lemma}\label{3.8} اگر $v>15$ و $E(v-6)=P(v-6)$ ، آنگاه یک $T(s,v)$ برای تمام $s \in P(v)$ با $s\leq max(P(v-6))+4$ وجود دارد. \end{lemma} \begin{proof} چون $x \in P(v)$ نتیجه می‌گیریم $x \in \lbrace y+4 : y \in P(v-6) \rbrace $ یا $x > max(P(v-6))+4$ ، پس چون می‌توانیم با استفاده از لم \ref{3.3} با $n=0$ ، یک $T(s+4,v)$ را از $T(4,6)$ و یک $T(s,v-6)$ بسازیم، نتیجه بدست می‌آید. \end{proof} \begin{lemma}\label{3.9} اگر $E(u)=P(u)$ برای تمام $u \leq v$ ، آنگاه یک $T(s,v)$ برای تمام $s$ و $v$ داده شده در جدول وجود دارد.\\ \begin{center} \begin{tabular}{|c|c|} \hline$ s $ &$ v $\\ \hline $ 4x+6 \geq s \geq 6x^2 -2x-1 $ & $ v = 6x \geq 18 $\\ $ 4x+6 \leq s \leq 6x^2 +x-4 $ & $ v = 6x+1 \geq 19 $\\ $ 4x+10 \leq s \leq 6x^2 +2x-1 $ & $ v = 6x+2 \geq 14 $\\ $ 4x+6 \leq s \leq 6x^2+ 5x-3 $ & $ v = 6x+3 \geq 21 $\\ $ 4x+10 \leq s \leq 6x^2 +6x $ & $ v = 6x+4 \geq 16$\\ $ 4x+10 \leq s \leq 6x^2 +7x$ & $ v = 6x+5 \geq 17 $\\ \hline \end{tabular}\\ \end{center} \end{lemma} \begin{proof} هر بار یکی از حالت‌های $v \equiv 0,1, \ldots ,5 ( \textsc{ mod} \; 6)$ را درنظرمی‌گیریم. \underline{$v=6x$}\\ طبق لم \ref{3.7} می‌توانیم فرض کنیم که $x \geq 3$ است. بنابراین $2x \geq 6$ ، پس یک جفت سیستم سه‌گانه تقسیم‌پذیر گروهی با $3$ گروه از اندازه $2x$ با اشتراک از اندازه $I$ برای هر\\ $I \in \lbrace 0,1,2, \ldots ,4x^2-6, 4x^2-4, 4x^2 \rbrace $ وجود دارد. طبق قسمت (1) لم \ref{3.5} ، وقتی \\ $x=3$ باشد، می‌توانیم از $T(4,6)$ همراه با سیستم سه‌گانه تقسیم‌پذیر گروهی با $I=1,2,\ldots ,30$ برای ساختن $T(47,18), T(46,18), \ldots, T(18,18)$ استفاده کنیم. وقتی $x=4$ ، می‌توانیم از سیستم سه‌گانه تقسیم‌پذیر گروهی با $I=1,2,\dots , 58,60, 64$ همراه با $T(6,8)$ و $T(8,8)$ برای ساختن $T(22,24), T(24,24),T(25,24), \ldots, T(87,24)$ استفاده کنیم. یک $T(23,24)$ می‌تواند با استفاده از $T(11,12)$ و $T(12,12)$ ساخته شود.\\ وقتی $x\geq 5$ ، یک $T(s,2x)$ برای تمام اعداد صحیح $s$ که $\lfloor (4x+6)/3\rfloor \leq s \leq \lceil (2x^2-2x-1)/3 \rceil $ وجود دارد. چون $2x^2-2x-1-(4x+6) > 6$ (وقتی که $x \geq 5$ )، این ترید‌ها می‌توانند به همراه سیستم‌های سه‌گانه تقسیم‌پذیر گروهی با $I=0,1,\dots , x^2-6, x^2$ برای ساختن\\ $T(4x+6,6x) , T(4x+7,6x),\ldots ,T(6x^2-2x-1,6x)$ استفاده شوند.\\ \underline{$v=6x+1$}\\ طبق لم \ref{3.7} می‌توانیم فرض کنیم که $x \geq 3$ است. بنابراین $2x \geq 6$ است، پس یک جفت از سیستم‌های سه‌گانه‌ی تقسیم‌پذیر گروهی با $3$ گروه از اندازه $2x$ و با اشتراک‌هایی از اندازه‌ی $I$ برای هر\\ $I \in \lbrace 0,1, \ldots ,4x^2-6, 4x^2-4, 4x^2 \rbrace $ وجود دارد.\\ طبق قسمت (2) لم \ref{3.5} وقتی $x=3$ می‌توانیم از $T(6,7)$ و $T(7,7)$ همراه با سیستم سه‌گانه تقسیم‌پذیر گروهی با $I=1,2,\ldots ,30,32,36$ برای ساختن $T(18,19), T(19,19), \ldots, T(53,19)$ استفاده کنیم. \\ وقتی‌که $x \geq 4$ باشد، یک $T(s,2x+1)$ برای تمام اعداد صحیح $s$ که\\ $\lfloor (4x+6)/3\rfloor \leq s \leq \lceil (2x^2+x-4)/3 \rceil $ ، وجود دارد. چون $2x^2+x-4-(4x+6) > 6$ ( وقتی $x \geq 4$ باشد)، این ترید‌ها می‌توانند به همراه سیستم‌های سه‌گانه تقسیم‌پذیر گروهی با\\ $I=0,1,\ldots , x^2-6, x^2$ برای ساختن\\ $T(4x+6,6x+1) , T(4x+7,6x+1),\ldots ,T(6x^2+x-4,6x+1)$ استفاده شوند.\\ \underline{$v=6x+2$}\\ طبق لم \ref{3.7} می‌توانیم فرض کنیم که $x \geq 3$ است. بنابراین $2x \geq 6$ است و پس یک جفت سیستم سه‌گانه تقسیم‌پذیر گروهی با $3$ گروه از اندازه $2x$ با اشتراک از اندازه $I$ برای هر\\ $I \in \lbrace 0,1,2, \ldots ,4x^2-6, 4x^2-4, 4x^2 \rbrace $ وجود دارد.\\ طبق قسمت (3) لم \ref{3.5} ، وقتی $x=3$ می‌توانیم از $T(6,8), T(7,7)$ و $T(8,8)$ همراه با سیستم سه‌گانه تقسیم‌پذیر گروهی با $I=1,2,\ldots ,30,32,36$ برای ساختن $T(22,20), T(23,20), \ldots, T(59,20)$ استفاده کنیم. \\ وقتی $x\geq 4$ ، یک $T(s,2x+2)$ با یک جفت رأس مستقل (چون $2x+2$ زوج است) برای تمام اعداد صحیح $s$ که $\lfloor (4x+10)/3\rfloor \leq s \leq \lceil (2x^2+2x-1)/3 \rceil $ وجود دارد. چون $2x^2+2x-1-(4x+10) > 6$ است (وقتی‌که $x \geq 4$ باشد)، این ترید‌ها می‌توانند به همراه سیستم‌های سه‌گانه تقسیم‌پذیر گروهی با $I=0,1,\dots , x^2-6, x^2$ برای ساختن $T(4x+10,6x+2) ,$\\ $ T(4x+11,6x+2),\ldots ,T(6x^2+2x-1,6x+2)$ استفاده شوند.\\ \underline{$v=6x+3$}\\ طبق لم \ref{3.7} می‌توانیم فرض کنیم که $x \geq 3$ است. بنابراین $2x+1> 6$ ، پس یک جفت سیستم سه‌گانه تقسیم‌پذیر گروهی با $3$ گروه از اندازه $2x+1$ با اشتراک از اندازه $I$ برای هر\\ $I \in \lbrace 0,1,2, \ldots ,4x^2+4x+1-6, 4x^2+4x+1-4, 4x^2+4x+1 \rbrace $ وجود دارد\\. طبق قسمت (1) لم \ref{3.5} ، وقتی $x=3$ می‌توانیم از $T(6,7)$ و $T(7,7)$ همراه با سیستم سه‌گانه تقسیم‌پذیر گروهی با $I=1,2,\ldots ,30,32,36$ برای ساختن $T(18,21), T(19,21), \ldots, T(66,21)$ استفاده کنیم. \\ وقتی $x\geq 4$ باشد، یک $T(s,2x+1)$ برای تمام اعداد صحیح $s$ که\\ $\lfloor (4x+6)/3\rfloor \leq s \leq \lceil (2x^2+x-4)/3 \rceil $ وجود دارد. چون $2x^2+x-4-(4x+6) > 6$ (وقتی که $x \geq 4$ )، این ترید‌ها می‌توانند به همراه سیستم‌های سه‌گانه تقسیم‌پذیر گروهی با $I=0,1,\dots , x^2-6, x^2$ برای ساختن $T(4x+6,6x+3) , T(4x+7,6x+3),\ldots ,T(6x^2+5x-3,6x+3)$ استفاده شوند.\\ \underline{$v=6x+4$}\\ طبق لم \ref{3.7} می‌توانیم فرض کنیم که $x \geq 3$ است. بنابراین $2x+1\geq 5$ ، پس یک جفت سیستم سه‌گانه تقسیم‌پذیر گروهی با $3$ گروه از اندازه $2x+1$ با اشتراک از اندازه $I$ برای هر\\ $I \in \lbrace 0,1,2, \ldots ,4x^2+4x+1-6, 4x^2+4x+1-4, 4x^2+4x+1 \rbrace $ وجود دارد. طبق قسمت (2) لم \ref{3.5} ، وقتی $x=2$ می‌توانیم از $T(4,6)$ همراه با سیستم سه‌گانه تقسیم‌پذیر گروهی با $I=1,2,\ldots ,19$ برای ساختن $T(18,16), T(19,16), \ldots, T(36,16)$ استفاده کنیم. \\ طبق قسمت (2) لم \ref{3.5} ، وقتی $x=3$ می‌توانیم از $T(6,8),T(7,7)$ $T(8,8)$ همراه با سیستم سه‌گانه تقسیم‌پذیر گروهی با $I=1,2,\ldots ,19$ برای ساختن $T(22,22), T(23,22), \ldots, T(72,22)$ استفاده کنیم. وقتی $x\geq 4$ است، یک $T(s,2x+2)$ برای تمام اعداد صحیح $s$ که\\ $\lfloor (4x+10)/3\rfloor \leq s \leq \lceil (2x^2+2x-1)/3 \rceil $ وجود دارد. چون $2x^2+2x-1-(4x+10) > 6$ است(وقتی که $x \geq 4$ باشد) ، این ترید‌ها می‌توانند به همراه با سیستم‌های سه‌گانه تقسیم‌پذیر گروهی با $I=0,1,\dots , x^2-6, x^2$ برای ساختن ترید‌های\\ $T(4x+10,6x+4) , T(4x+11,6x+4),\ldots ,T(6x^2+6x,6x+4)$ استفاده شوند.\\ \underline{$v=6x+5$}\\ طبق لم \ref{3.7} می‌توانیم فرض کنیم که $x \geq 2.$ بنابراین $2x+1\geq 5$ و پس یک جفت سیستم سه‌گانه تقسیم‌پذیر گروهی با $3$ گروه از اندازه $2x+1$ با اشتراک از اندازه $I$ برای هر\\ $I \in \lbrace 0,1,2, \ldots ,4x^2+4x+1-6, 4x^2+4x+1-4, 4x^2+4x+1 \rbrace $ وجود دارد\\ طبق قسمت (3) لم \ref{3.5} ، وقتی $x=2$ می‌توانیم از $T(4,6),T(6,7)$ $T(7,7)$ همراه با سیستم سه‌گانه تقسیم‌پذیر گروهی با $I=1,2,\ldots ,19,21,25$ برای ساختن\\ $T(18,17), T(19,17), \ldots, T(38,17)$ استفاده کنیم. \\ طبق قسمت (3) لم \ref{3.5} ، وقتی‌که $x=3$ می‌توانیم از $T(6,8),T(8,8),T(8,9),T(9,9),T(10,9)$ همراه با سیستم سه‌گانه تقسیم‌پذیر گروهی با $I=1,2,\ldots ,19$ برای ساختن ترید‌های\\ $T(22,22), T(23,22), \ldots, T(75,22)$ استفاده کنیم. \\ وقتی‌که $x\geq 4$ ، یک $T(s,2x+3)$ برای تمام اعداد صحیح $s$ که\\ $\lfloor (4x+10)/3\rfloor \leq s \leq \lceil (2x^2+5x-1)/3 \rceil $ وجود دارد. اما در این حالت نمی‌توانیم تضمین کنیم که تمام این ترید‌ها یک جفت رأس مستقل خواهند داشت، اما یک ترید از مرتبه $ 2x+2 $ شامل یک جفت رأس مستقل است.\\ $ T(s,2x+2) $ برای تمام اعداد صحیح $ s $ که $\lfloor (4x+10)/3\rfloor \leq s \leq \lceil (2x^2+2x-1)/3 \rceil $ وجود دارد. اما ترید با بیشترین حجمی که می‌توانیم بسازیم با $ I=(2x+1)^2 $ ، از حجم \\ $ \lceil 2\dfrac{2x^2+2x-1}{3} \rceil + \lceil \dfrac{2x^2+5x-1}{3} \rceil $ است که این مقدار حداقل برابر با $ 2x^2+3x-1 $ است. چون $2x^2+3x-1-(4x+10) > 6$ (وقتی که $x \geq 4$ )، این ترید‌ها می‌توانند به همراه سیستم‌های سه‌گانه تقسیم‌پذیر گروهی با $I=0,1,\dots , x^2-6, x^2$ برای ساختن تریدهای\\ $T(4x+10,6x+5) , T(4x+11,6x+5), \ldots ,T(6x^2+7x,6x+5)$ استفاده شوند. \end{proof} حال قضیه اصلی این قسمت را بیان می‌کنیم. \begin{theorem} برای تمام اعداد صحیح $v$ ، $E(v)=P(v) $ است. \end{theorem} \begin{proof} با استقراء روی $v$ ثابت می‌کنیم. مانند نتایج $E(v)=P(v)$ برای $v \leq 15$ (لم \ref{3.7} را ببینید) از سه نتیجه‌ی وجودی لم‌های \ref{3.8} و \ref{3.9} و نتیجه‌ی \ref{3.2} استفاده می‌کنیم. به این‌ها به ترتیب به عنوان ساختار حجم کوچک، متوسط و بزرگ اشاره می‌کنیم. تمام نیاز ما این است که نشان دهیم :\\ $(1)$ ساختار حجم کوچک ترید‌هایی از تمام حجم‌های ممکن مثلاً کوچک‌تر مساوی $\ s_1$ را می‌دهد؛\\ $(2)$ ساختار حجم بزرگ ترید‌هایی از تمام حجم‌های ممکن مثلاً بزرگ‌تر مساوی $ s_2$ را می‌دهد؛\\ $(3)$ ساختار حجم متوسط ترید‌هایی از تمام حجم‌های ممکن مثلاً $s$ که $s_1 < s< s_2$ را می‌دهد.\\ به سادگی بررسی می‌شود که این شرایط برقرار هستند. با درنظرگرفتن تریدهایی از مرتبه‌های همنهشت با هر باقی‌مانده به پیمانه‌ی $ 6 $ به صورت جداگانه. \end{proof} \section{طیف $ -C_4 $ترید } یک ترید در این بخش به معنی یک $-4$ دور ترید است و وقتی می‌نویسیم $T(s,v)$ به معنی یک ترید از حجم $s$ و بنیان $v$ است. \begin{example} یک $-C_4$ ترید روی گراف $K_{2,4}$ ، $T(2,6) $ در شکل \ref{c4,1} داده شده‌است که دو کپی از گراف دوبخشی کامل $K_{2,4}$ را نشان می‌دهد که در هر کدام یک افراز از مجموعه یال‌های گراف $K_{2,4}$ را به $-4$ دورها را نشان می‌دهد. این‌جا \[T_1 =\lbrace (a,c,b,d) , (a,e,b,f) \rbrace\] و \[T_2 =\lbrace (a,c,b,f) , (a,d,b,e) \rbrace. \] این ترید حجم $s=2$ و بنیان $v=6$ دارد. \end{example} \begin{figure}[h] \centering \includegraphics[width=10cm]{c4,1.jpg} \caption{ ترید$-C_4$روی گراف $ K_{2,4}$ } \label{c4,1} \end{figure} این ترید به آسانی به یک ترید روی $K_{2,2n}$ برای تمام $n\geq 2$ تعمیم داده می‌شود. نتیجه اصلی ما در این بخش این است که؛\\ برای $v \geq 6$ یک $T(s,v)$ وجود دارد اگر و فقط اگر $m(v) \leq s \leq M(v)$ که $m(v) $ و $ M(v)$ به صورت زیر تعریف می‌شوند:\\ \begin{equation*} M(v) = \left\{ \begin{array}{ll} v(v-2)/8 & v\equiv 0 (\textsc{ mod} \; 2)\text{اگر } \\ v(v-1)/8 & v\equiv 1 ( \textsc{ mod} \; 8 )\text{اگر } \\ (v^2-v-6)/8 & v\equiv 3 ( \textsc{ mod} \; 8 ) \text{اگر } \\ (v^2-v-12)/8 & v\equiv 5 (\textsc{ mod} \; 8 )\text{اگر } \\ (v^2-v-10)/8 & v\equiv 7 (\textsc{ mod} \; 8)\text{اگر } \end{array} \right. \end{equation*} \begin{equation*} m(v) = \left\{ \begin{array}{ll} v/3 & \; v\equiv 0 (\textsc{ mod} \;6) \text{اگر }\\ \lceil (v-1) /3 \rceil & \;v\not\equiv 0 ( \textsc{ mod} \; 6)\text{اگر } \end{array} \right. \end{equation*} واضح است که اگر حجم $s$ بیش از تعداد $-4$ دورها در یک ماکسیمم بسته بندی از $K_v$ باشد، که برابر $M(v)$ است، ترید $T(s,v)$ نمی‌تواند وجود داشته باشد.\\ همچنین به سادگی دیده می‌شود که، برای هر $v$ $(v \geq 6)$ ، $ m(v)$ کمترین مقدار $s$ است که برای آن یک $T(s,v)$ وجود دارد( می‌توان از لم \ref{62.1} نیز برای اثبات کران پایین روی $s$ استفاده کرد).\\ \begin{lemma}\label{2.10} فرض کنید که یک $T(s,v)$ وجود دارد. آنگاه $v\leq 3s$ است، و اگر $s$ فرد باشد، آنگاه $v \leq 3s-1$ است. \end{lemma} \begin{proof} فرض کنید که $G$ گراف اساسی یک $T(s,v)$ است. آنگاه تمام رأس‌های $G$ باید از درجه زوج باشند(چون اجتماعی از دور‌هایی به طول چهار است). فرض کنید $x$ تعداد رأس‌های درجه $2$ و $y$ تعداد رأس‌های از درجه حداقل $4$ تعریف شود. به آسانی دیده می‌شود که هیچ دو رأس از درجه $2$ نمی‌تواند با یالی از $G$ متصل باشند(در این صورت این یال تنها در یک دور واقع می‌شود) زیرا که این مانع وجود یک ترید روی $G$ می‌شود.چون هر رأس درجه دو، $2$ یال مجزا دارد و هر بلوک چهار یال دارد، بنابراین $2x \leq 4s$ و چون $2x+4y $ حداکثر مجموع درجه رأس‌های $G$ است، همچنین داریم $2x+4y \leq 8s$. با ترکیب این دو نامساوی داریم $v=x+y \leq 3s$. حال فرض می‌کنیم که یک $T(s,3s)$ وجود دارد. آنگاه نامساوی‌های اخیر باید تساوی باشند پس $y=s$ و $x=2s$ است، و هر رأس‌ با درجه‌ی بزرگ‌تر از $2$ در $G$ باید از درجه‌ی $4$ باشد. به علاوه، $G$ دوبخشی است با رأس‌هایی از درجه‌ی $2$ و رأس‌هایی از درجه‌ی $4$ دوبخشی می‌شود. چون $G$ گراف اساسی یک $T(s,v)$ است، $G$ اجتماعی یال مجزا از یک مجموعه از $-4$ دورهاست. یک رأس، $a$ ، از درجه‌ی $2$ را انتخاب کنید و فرض کنید $B,A$ دو رأس از درجه‌ی $4$ هستند که با $a$ مجاورند. برای تشکیل یک $-4$ دور، $A$ و $B$ باید به رأس دیگری مانند $b$ از درجه‌ی $2$ متصل باشند.\\ حال نیاز داریم نشان دهیم که $A$ و $B$ با هم در یک $-4$ دور دیگر واقع می‌شوند. فرض کنید این‌طور نیست. آنگاه $a$ و $b$ تنها رأس‌هایی هستند که با هر دوی $A$ و $B$ مجاورند، پس هر $-4$ دور شامل یال‌های $aA$ و $aB $ باید شامل یال‌های $bA$ و $bB $ نیز باشد، که این مسأله مانع از وجود یک ترید روی $G$ می‌شود. بنابراین $A$ و $B$ باید با هم در یک $-4$ دور دیگر نیز واقع شوند.\\ پس $A$ و $B$ باید به یک رأس سوم $c$ از درجه‌ی $2$ متصل باشند، و همچنین به رأس چهارم $d$ از درجه‌ی $2$. اما آنگاه شش رأس $B ,A,d,c,b,a$ و یال‌های شرح داده شده‌ی اخیر تشکیل یک $K_{2,4}$ مولفه ناهمبندی از $G$ را می‌دهند. نتیجه می‌شود که $G$ به کپی‌های مجزا از $K_{2,4}$ تجزیه پذیر است و در نتیجه، تعداد رأس‌های درجه‌ی $4$ باید زوج باشند. بنابراین اگر $v=3s$ باشد، $s$ باید زوج باشد. پس، اگر $s$ فرد باشد، $v \leq 3s-1$ است. \end{proof} \begin{corollary} اگر $v \geq 6$ باشد، هیچ $T(s,v)$ برای $s (v-1)/3$ است. پس باید $s \geq m(v)$ باشد. \end{proof} دو تکنیک ساختار اساسی برای اثبات کفایت شرط وجود ترید به کار می‌بریم. اولی یک $T(s,v)$ را برای مقادیر کوچک $s$ ، از $m(v)$ حداکثر تا تقریباً $v$ را تولید می‌کند، و دومی برای مقادیر بزرگ $s$ ، از تقریباً $3v/8$ تا حداکثر $M(v) $ را ایجاد می‌کند. برای اعداد صحیح $a$ و $b$ که $(a \leq b)$ برای تعریف مجموعه تمام اعداد صحیح $x$ که $a \leq x \leq b$ از نماد $[a,b]$ استفاده می‌کنیم.\\ \subsection{مقادیر کوچک $s$} \begin{lemma}\label{2.11} فرض کنید که $v \geq 6$ و زوج است. آنگاه یک $T(s,v)$ برای $m(v) \leq s \leq v-4$ وجود دارد. \end{lemma} \begin{proof} در ابتدا، یک عدد صحیح $k$ که در $0 \leq k \leq\lfloor (v-6)/3 \rfloor$ صدق می‌کند را درنظربگیرید و $B,A$ را دو مجموعه مجزا از رأس‌ها درنظربگیرید که $\vert A \vert =v-4-2k$ و $\vert B \vert =4+2k$ است. مجموعه $A$ به $(v-4-2k)/2$ زوج مجزا افراز می‌شود و هر زوج را به عنوان یکی از مجموعه رأس‌های یک کپی از $K_{2,4}$ درنظربگیرید، که مجموعه رأس دیگر آن شامل $4$ رأس انتخاب شده از $B$ ‌است. چون $k \leq (v-6)/3$ ، داریم $4(\frac{v-4-2k}{2}) \geq 4+2k$ ، پس می‌توانیم به مجموعه‌های $4$ رأسی انتخاب شده از $B$ نظم دهیم تا تمام $B $ را بپوشاند. گراف $G$ تشکیل شده از کپی‌هایی از $K_{2,4}$ یک ترید $T(v-4-2k,v)$ می‌دهد(زیرا هر $K_{2,4}$ یک ترید از حجم دو می‌دهد). در این روش یک $T(s,v)$ را برای $s=v-4, v-6, \ldots , v-4-2\lfloor (v-6)/3 \rfloor $ بدست می‌آوریم.\\ بعد مشاهده می‌کنیم که یکی از گراف‌های $K_{2,4}$ می‌تواند با یک $K_{2,6}$ جایگزین شود، با شرط این‌که $\vert B \vert \geq 6$ ، یعنی $k \geq 1$ باشد. این کار حجم ترید را $1$ واحد افزایش می‌دهد( زیرا هر $K_{2,6}$ تریدی از حجم سه می‌دهد). درنتیجه مجموعه‌‌ای از شش رأس انتخاب شده از $B$ به همراه مجموعه‌های باقی‌مانده از چهار رأس انتخاب شده می‌تواند $B$ را با شرط $k \leq \lfloor (v-5)/3 \rfloor$ بپوشاند. بنابراین یک $T(s,v)$ را برای حجم‌های\\ $s=v-5,v-7,\ldots ,v-3-2\lfloor (v-5)/3 \rfloor$ نیز بدست می‌آوریم.\\ ترکیب دو نتیجه یک $T(s,v)$ برای $m(v) \leq s \leq v-4$ را می‌دهد. \end{proof} \begin{lemma}\label{2.12} فرض کنید $v \geq 9$ ، و فرد است. آنگاه یک $T(s,v)$ برای $m(v) \leq s \leq v-5$ وجود دارد. اگر $v=7$ باشد آنگاه یک $T(s,v)$ برای $s= m(7)=3$ وجود دارد. \end{lemma} \begin{proof} برای $v \geq 9$ استدلال همانند لم قبل است اما با $\vert A \vert=v-5-2k$ و $\vert B \vert =5+2k$ . تجزیه به کپی‌هایی از $K_{2,4}$ یک $T(s,v)$ برای $s=v-5, v-7, \ldots , v-5-2 \lfloor (2v-15)/6 \rfloor$ را می‌دهد. گنجاندن یک $K_{2,6}$ (برای $v \geq 11$ ) یک $T(s,v)$ برای $s=v-6, v-8, \ldots , v-4-2 \lfloor (2v-13)/6 \rfloor$ می‌دهد. ترکیب این‌ها یک $T(s,v)$ برای $m(v) \leq s \leq v-5$ را می‌دهد.\\ یک $T(3,7)$ روی رأس‌های $6,5,4,3,2,1,0$ نیز با $T_1 = \lbrace (0,3,5,6) , (1,4,3,6) , (2,5,4,6) \rbrace$ و $T_2 = \lbrace (0,3,4,6) , (1,4,5,6) , (2,5,3,6) \rbrace$ داده شده‌است. \end{proof} \subsection{مقادیر بزرگ $s$} در این بخش ابتدا یک توضیح کلی از ساختار می‌دهیم. این ساختار از تعدادی از ترید‌های کوچک استفاده می‌کند ابتدا آن‌هایی که نیاز است و قبلاً در بخش قبل ساخته نشده‌اند را تولید می‌کنیم. سپس ساختار را تنها با درنظرگرفتن هشت کلاس باقی‌مانده برای $v$ به پیمانه $8$ به کار می‌گیریم.\\ اساس ساختار در شکل \ref{c4,2} نشان داده شده‌است که $\vert A \vert+ \vert B \vert =r $ ، $\vert D_i \vert= 8$ برای $(i=1,2,\ldots , t-1)$ است و $v=8(t-1)+r$.\\ این‌جا $B,A$ و $ ( i=1,2,\ldots,t-1 ) D_i$ مجموعه‌های مجزا از رأس‌ها هستند که اجتماعی از $8(t-1)+r$ رأس از گراف $G$ خواهند بود. روی $A \cup B$ یک زیرگراف فراگیر مناسب $H$ از $K_r$ انتخاب شده‌‌است و یک ترید $(S_1,S_2)$ روی $H$ قرار می‌دهیم. روی هر $A \cup D_i$ یک زیرگراف فراگیر $J_i$ از $K_{8+\vert A \vert}$ انتخاب شده‌است و یک ترید $(U'_1,U'_2)$ روی $J_i$ قرار می‌دهیم. روی هر $B \cup D_i$ یا هیچ یال اضافی قرار نمی‌دهیم یا یک زیرگراف فراگیر $L_i$ از $K_{\vert B \vert ,8}$ ( با دو بخش $\lbrace B , D_i \rbrace$ )انتخاب می‌کنیم و یک ترید $( V'_1,V'_2)$ روی $L_i$ قرار می‌دهیم. در آخر روی هر $D_i \cup D_j (0 \leq i < j \leq t-1)$ یا هیچ یال اضافی قرار نمی‌دهیم یا یک زیرگراف فراگیر مناسب $M_{i,j}$ از $K_{8,8}$ (با دو بخش $\lbrace D_i , D_j \rbrace$ ) انتخاب می‌کنیم و یک ترید $(W^{i,j}_i , W^{i,j}_2)$ روی $M_{i,j}$ قرار می‌دهیم.\\ در این بخش به میزان قابل توجهی در انتخاب $H,J_i,L_i$ و $M_{i,j}$ ،و ترید‌های وابسته انعطاف‌پذیری وجود دارد. اما برای تولید ترید مجاز روی گراف حاصل $G$ باید مطمئن باشیم که $G$ ساده و بدون رأس تنها است. خواهیم دید که این به راحتی می‌تواند برای ترید‌های کلی از حجم $s$ در محدوده‌ی از $M(v)$ به پایین تا( تقریباً) $3v/8$ بدست آید.\\ حال ترید‌های کوچک مورد نیاز برای ساختار را بدست می‌آوریم. \begin{figure}[t] \centering \includegraphics[width=11cm]{c4,2.jpg} \caption{ ساختار } \label{c4,2} \end{figure} \begin{lemma}\label{2.13} برای هر عدد صحیح مثبت $n$ ، یک ترید از حجم $s$ روی یک زیرگراف $K_{2n,8}$ برای $s \in [2,4n]$ وجود دارد. \end{lemma} \begin{proof} گراف $K_{2n,8}$ به $n$ کپی از $K_{2,8}$ می‌تواند تجزیه شود. به علاوه $K_{2,8}$ ، گراف‌های $K_{2,4}$ و $K_{2,6}$ را به عنوان زیرگراف دارد. چون ترید از حجم $2$ ، $3$ و $4$ به ترتیب روی $K_{2,4}$ ، $K_{2,6}$ و $K_{2,8}$ وجود دارد، نتیجه حاصل می‌شود. \end{proof} \begin{lemma}\label{2.14} یک $T(s,8)$ برای هر $s \in [3,6]$ وجود دارد. \end{lemma} \begin{proof} لم \ref{2.11} به $s=3$ و $s=4$ می‌پردازد. برای $s >4$ مجموعه رأس را $[0,7]$ درنظربگیرید. $K_{2,6}$ را با دو بخش $\lbrace [0,1] , [2,7] \rbrace$ به روی این رأس‌ها و $K_{2,4}$ به روی $[2,7]$ قرار دهید. گراف حاصل یک ترید با حجم $s=3+2=5$ دارد. برای پرداختن به $s=6$ ، $K_{2,6}$ را مانند قبل درنظربگیرید و $K_{2,2,2}$ را به روی $[2,7]$ قرار دهید. مشاهده می‌کنید که $K_{2,2,2}$ یک ترید ازحجم $3$ دارد که با \begin{flushleft} $T_1= \lbrace (2,4,3,5) , (2,6,5,7) , (3,6,4,7) \rbrace,$ $T_2= \lbrace (2,4,6,5) , (2,6,3,7) , (3,4,7,5) \rbrace,$ \end{flushleft} داده شده‌است. بنابراین گراف تشکیل شده از $K_{2,6}$ و $K_{2,2,2}$ یک ترید از حجم $ s=3+3=6$ دارد. \end{proof} \begin{lemma}\label{2.15} یک $T(s,9)$ برای هر $s \in [4,9]$ وجود دارد. \end{lemma} \begin{proof} لم \ref{2.12} به $s=4$ می‌پردازد. برای $s >4$ مجموعه رأس را $[0,8]$ درنظربگیرید. مشاهده می‌کنید که $K_9$ به سه گراف زیر تجزیه می‌شود(شکل \ref{c4,3} را ببنید). \begin{figure}[t] \centering \includegraphics[width=13cm]{c4,3.jpg} \caption{ ‌سه گراف حاصل از تجزیه‌ی $ K_9 $} \label{c4,3} \end{figure} ترید‌هایی از حجم $2$ و $3$ به ترتیب روی $K_{2,4}$ و $K^*$ (برای حالت دوم $T(3,7)$ که در اثبات لم \ref{2.12} ارائه داده شد را ببینید) وجود دارند. یک ترید $\{T_1,T_2\}$ روی $K'$ از حجم $4$ با \[T_1= \lbrace (0,1,3,2) , (0,3,5,4) , (1,2,6,4) , (2,7,3,4)\rbrace, \] و \[T_2= \lbrace (0,1,2,4) , (0,2,7,3) , (1,3,5,4) , (2,6,4,3)\rbrace, \] داده شده‌است، و یک ترید $\{ S_1, S_2\}$ از حجم $3$ روی یک زیرگراف $K''$ از $K'$ با \[S_1 = \lbrace (0,1,3,2) , (1,2,6,4) , (2,7,3,4) \rbrace, \] و \[S_2 = \lbrace (0,1,4,2) , (1,2,7,3) , (2,3,4,6) \rbrace, \] داده شده‌است.\\ با درنظرگرفتن $K_9$ به عنوان ترکیب $K^* , K_{2,4}$ و $K'$ ، واضح است که یک $T(s, 9)$ برای $s=9$ وجود دارد. جایگزینی $K'$ با $K''$ ، $s=8$ را می‌دهد. درنظرگرفتن فقط $K^*$ و $K'$ ، ترید از حجم $s=7$ را می‌دهد، درنظرگرفتن فقط $K^*$ و $K''$ ، ترید از حجم $s=6$ را می‌دهد، و در نهایت، درنظرگرفتن فقط $K_{2,4}$ و $K^*$ ، ترید از حجم $s=5$ را می‌دهد. \end{proof} \begin{lemma}\label{2.16} یک $T(s, 10)$ برای هر $s \in [4, 10]$ وجود دارد. \end{lemma} \begin{proof} لم \ref{2.11} به تریدهایی با حجم $s= 4,5,6$ می‌پردازد. برای $s >6$ مجموعه رأس $[0,9]$ را درنظربگیرید. $K_{2,8}$ را با دو بخش $\lbrace [0,1] , [2,9] \rbrace$ به‌روی این رأس‌ها قرار دهید، $K_{2,6}$ را با دو بخش $\lbrace [2,3] ,[4,9] \rbrace$ به‌روی $[2,9]$ و $K_{2,2,2}$ را به‌روی $[4,9]$ قرار دهید. گراف حاصل یک ترید از حجم $s =4+3+3=10$ دارد. جایگزینی $K_{2,6}$ با $K_{2,4}$ با دو بخش $\lbrace [2,3] ,[4,7]\rbrace$ به $s=9$ می‌پردازد، و به علاوه جایگزینی $K_{2,2,2}$ با یک $K_{2,4}$ دیگر با دو بخش $\lbrace [4,5] ,[6,9] \rbrace$ به حجم‌ $s=8$ می‌پردازد. برای $s=7$ ، گراف اصلی را برمی‌گردانیم و $K_{2,2,2}$ را حذف می‌کنیم. \end{proof} \begin{lemma}\label{2.17} برای هر $s \in [4, 13]$ یک $T(s, 11)$ که گراف اساسی یک زیرگراف $K_{11}-C_3$ است وجود دارد. \end{lemma} \begin{proof} ساختار لم \ref{2.12} برای حجم‌های $s=4,5,6$ را نتیجه می‌دهد. برای $s > 6$ مجموعه رأس $[0,10]$ را درنظربگیرید. $C_3$ را روی $[0,2]$ درنظربگیرید، $K_{11}-C_3$ را می‌توان به $K_9$ روی $[2,10]$ و $K_{2,8}$ با دو بخش $\lbrace [0,1] ,[3,10]\rbrace$ تجزیه کرد. اولی زیرگراف‌هایی دارد که ترید‌های $T(s , 9)$ برای $s \in [4,9]$ را طبق لم \ref{2.15} می‌دهد، و دومی زیرگراف $K_{2,6}$ را دارد. بنابراین ترید‌های $T(s,11)$ که گراف‌های اساسی زیرگراف‌هایی از $K_{11}-C_3$ هستند برای مقادیر $s$ از $9+4=13$ به پایین تا $4+3=7$ وجود دارد. \end{proof} \begin{lemma}\label{2.18} یک $T(s, 12)$ برای هر $s \in [4,15]$ وجود دارد. \end{lemma} \begin{proof} لم \ref{2.11} به ترید با حجم $s \in [4,8]$ می‌پردازد. برای $s > 8$ ، مجموعه رأس $[0,11]$ را درنظربگیرید. $K_{2,10}$ را با دو بخش $\lbrace [0,1] ,[2, 11] \rbrace$ به‌روی این رأس‌ها قرار دهید پس از آن $K_{2,8}$ را با دو بخش $\lbrace [2,3] ,[4, 11] \rbrace$ ، $K_{2,6}$ را با دو بخش $\lbrace [4,5] ,[6,11] \rbrace$ ، و در آخر $K_{2,2,2}$ را روی رأس‌های $[6,11]$ . گراف حاصل یک ترید از حجم $s=5+4+3+3=15$ دارد. جایگزینی $K_{2,6}$ با یک زیرگراف $K_{2,4}$ به $s=14$ می‌پردازد. جایگزینی $K_{2,8}$ با یک زیرگراف $K_{2,4}$ (باقی ماندن $K_{2,6}$ ) به $s=13$ می‌پردازد. حذف $K_{2,2,2}$ از گراف اصلی به $s=12$ می‌پردازد، و حذف $K_{2,8}$ از گراف اصلی به $s=11$ می‌پردازد. حذف $K_{2,8}$ از گراف اصلی و جایگزینی $K_{2,6}$ با یک زیرگراف $K_{2,4}$ به‌ $s=10$ می‌پردازد. در نهایت، حذف $K_{2,2,2}$ و $K_{2,6}$ از گراف اصلی به $s=9$ می‌پردازد \end{proof} \begin{lemma}\label{2.19} برای هر $s \in [5,18]$ یک $T(s,13)$ که گراف اساسی یک زیرگراف $K_{13}-b$ (که $b$ یک گراف پروانه است) وجود دارد. \end{lemma} \begin{proof} لم \ref{2.12} به ترید با حجم $s \in [5,8]$ می‌پردازد. برای $s > 8$ ، مجموعه رأس $[0,12]$ را درنظربگیرید، و فرض کنید گراف $b$ یال‌های $01,02,12,23,24,34$ را دارد. آنگاه $K_{13}-b$ می‌تواند به $K_{2,10}$ با دو بخش $\lbrace [0,1] ,[3,12] \rbrace$ و $K_{11}-C_3$ روی $[2,12]$ با $C_3$ روی $[2,4]$ تجزیه شود. اولی یک ترید از حجم $5$ طبق لم \ref{2.17} دارد دومی یک زیرگراف‌هایی دارد که ترید‌های $T(s,11)$ را برای $s \in [4,13]$ می‌دهند. بنابراین ترید‌های $T(s,13)$ که گراف‌های اساسی زیرگراف‌هایی از $K_{13}-b$ هستند برای مقادیر $s$ از $5+13=18$ به پایین تا $5+4=9$ وجود دارد. \end{proof} \begin{lemma}\label{2.20} برای هر $s \in [5,17]$ یک $T(s,13)$ که گراف اساسی یک زیرگراف $K_{13}-K_5$ است وجود دارد. \end{lemma} \begin{proof} ساختار لم نتیجه را \ref{2.12} برای $s \in [5,8]$ می‌دهد. برای $ s> 8$ ، روش لم \ref{2.19} را دنبال می‌کنیم اما به جای $K_ { 2,10}$ از گراف $K_{2,8}$ با دو بخش $\lbrace [1,0] , [5,12]\rbrace$ استفاده می‌کنیم. این گراف همراه با $K_{11}-C_3$ گراف $K_{13}-K_5$ را تشکیل می‌دهند. چون $K_{2,8}$ یک ترید از حجم $4$ دارد، می‌توانیم ترید‌های $T(s,13)$ که گراف اساسی آن‌ها زیرگراف‌های $K_{13}-K_5$ هستند را برای مقادیری از $s$ از $4+13=17$ به پایین تا $4+4=8$ را تولید کنیم. \end{proof} \begin{lemma}\label{2.21} برای هر $s \in[6,25]$ یک $T(s,15)$ که گراف اساسی یک زیرگراف از $K_{15}-C_5$ است وجود دارد. \end{Lemma} \begin{proof} ساختار لم \ref{2.12} نتیجه را برای $s \in[6,25]$ می‌دهد. برای $s>10$ مجموعه رأس $[0,14]$ را درنظربگیرد و فرض کنید $C_5$ دور $(0,1,2,3,4)$ باشد. $K_7-C_5$ را روی رأس‌های $[0,6]$ قرار دهید. $K_{11}-C_3$ را روی رأس‌های $[2,14] \setminus [5,6]$ ( با $C_3$ روی $\lbrace 2,3,4 \rbrace$ ) قرار دهید. $K_{4,8}$ را با دو بخش $\lbrace \lbrace 0,1,5,6 \rbrace , [7,14] \rbrace $ به‌روی $[0,14] \setminus [2,4]$ قرار دهید. بنابراین $K_{15}-C_5$ به $K_7-C_5 , K_{11}-C_3$\\ و $K_{4,8}$ تجزیه می‌شود. اولی یک $T(4,7)$ ترید دارد که توسط \[T_1= \lbrace (0,2,4,6), (0,3,1,5) , (1,4,5,6) , (2,5,3,6) \rbrace, \] و \[T_2= \lbrace (0,2,6,5), (0,3,1,6) , (1,4,2,5) , (3,5,4,6) \rbrace,\] داده شدهاست؛ همچنین یک ترید $T(3,7)$ روی یک زیرگراف یکریخت با $K^*$ می‌دهد، که در اثبات لم \ref{2.15} شرح داده شده‌است. دومی طبق لم \ref{2.17} ، زیرگراف‌هایی با ترید‌های $T(s,11)$ برای $s \in [4,13]$ دارد. سومی زیرگراف‌هایی با تریدهایی از حجم‌های $8$ و $s=2,4,6$ دارد.\\ نتیجه می‌شود که $K_{15}-C_5$ زیرگراف‌هایی دارد که یک $T(s,15)$ برای مقادیر $s$ از $4+13+8=25$ به پایین تا $3+4+2=9$ را می‌دهد. \end{proof} \begin{lemma}\label{2.22} برای هر $s \in [6,21]$ یک $T(s,15)$ که گراف اساسی یک زیرگراف از $K_{15}-K_7$ است وجود دارد. \end{Lemma} \begin{proof} مجموعه رأس و گراف‌های $K_{11}-C_3$ و $K_{4,8}$ را مانند اثبات لم \ref{2.21} درنظربگیرید. بنابراین $K_{15}-K_7$ به $K_{11}-C_3$ و $K_{4,8}$ تجزیه می‌شود. اولی زیرگراف‌هایی دارد که ترید‌های $T(s,11)$ را برای $s \in [4,13]$ می‌دهد و دومی زیرگراف‌هایی با ترید‌هایی از حجم $8$ و $s=2,4,6$ دارد، و می‌توانیم مطمئن باشیم که رأس‌ها با برچسب $5,1,0$ و $6$ در هر یک از این زیرگراف‌ها غیر تنها هستند.\\ نتیجه می‌شود که $K_{15}-K_7$ زیرگراف‌هایی دارد که یک ترید $T(s,15)$ برای مقادیر $s$ از $13+8=21$ به پایین تا $4+2=6$ را می‌دهد. \end{proof} \begin{theorem} برای $v \geq 6$ و $s \in [m(v) , M(v)]$ یک ترید $T(s,v)$ وجود دارد. برای $v \leq 5$ هیچ $T(s,v)$ وجود ندارد. \end{theorem} \begin{proof} برای $v \geq 6$ اثبات را به هشت حالت تقسیم می‌کنیم، وابسته به باقیمانده $v$ به پیمانه $8$ . در حالت آخر مقدار $v=7$ را حذف می‌کنیم اما $m(7)=3$ و $M(7)=4$ وقبلاً یک $T(3,7)$ در لم \ref{2.12} و یک $T(4,7)$ در لم \ref{2.21} ارائه داده بودیم. \underline{$ v=8t ~~(t\geq 1)~~ (1)$.}\\ با توجه به شکل \ref{c4,2} ، $A=\emptyset$ ، $\vert B \vert = 8$ را درنظر می‌گیریم. $B$ را به عنوان $D_0$ درنظرمی‌گیریم. روی هر $D_i (0\leq i \leq t-1) $ ، می‌توانیم یک ترید $T(s_i ,8)$ قرار دهیم، که حجم $s_i$ هر یک از مقادیر $3,4,5$ یا $6$ است (لم \ref{2.14} را ببینید). روی هر $D_i \cup D_j ( 0\leq i 2I $، آنگاه یک $ T(b-I, v) $ وجود دارد. \end{lemma} \begin{proof} چون $ v-d-1>2I $، هر رأس در $ G\setminus (S_1 \cap S_2) $ قرار می‌گیرد. بنابراین $ G \setminus (S_1 \cap S_2) $ یک $ T(b-I, v) $ می‌دهد. \end{proof} یک ماکسیمم $-5$ دور بسته بندی از مرتبه $v$ یک $-5$ دور سیستم جزیی است که بیشترین تعداد $-5$ دورها را دارد(برای $v$ داده شده).\\ حل مسأله اشتراک برای ماکسیمم $-5$ دور بسته بندی در جدول \ref{T.3} خلاصه شده‌است، همراه با ماکسیمم درجه $d$ از مکمل هر ماکسیمم $-5$ دور بسته بندی.\\ یک $-5$ دور سیستم تقسیم‌پذیرگروهی با $m$ گروه از اندازه $n$ ، یک $-5$ دور سیستم جزیی، $(G,T)$ است که $G$ گراف چندبخشی کامل با $m$ بخش و $n$ رأس در هر بخش است.\\ مسأله اشتراک برای $-5$ دور سیستم‌های تقسیم‌پذیرگروهی با $m$ گروه از اندازه $n$ در \cite{gc5} حل شده‌است، که در آن نشان داده شده‌است، که یک جفت از چنین سیستم‌هایی با دقیقاً $k$ ، $-5$ دور مشترک برای هر $k$ ، که $k \in \{ 0,1,2, \ldots, (m(m-1)n^2) / 10 -2, (m(m-1)n^2) / 10 \}$ است، وجود دارد. با استفاده از حل مسأله اشتراک برای ماکسیمم $-5$ دور بسته بندی و لم \ref{2.5.1} ، $T(s,v)$ های داده‌شده در جدول \ref{T.4} را ‌بدست می‌آوریم. \begin{table}[h] \begin{center} \begin{tabular}{|c|c|c|} \hline $ d $ &مقادیر اشتراک‌های ممکن & $ v $\\ \hline $ 1 $& $ 0,1,\ldots ,\frac{v^2-2v}{10}-2,\frac{v^2-2v}{10} $ & $ v\equiv 0,2 (\textsc{ mod} \; 10) $ \\ $ 0 $& $ 0,1,\ldots ,\frac{v^2-v}{10}-2,\frac{v^2-v}{10} $ & $ v\equiv 1,5 (\textsc{ mod} \; 10) $ \\ $ 2 $& $ 0,1,\ldots ,\frac{v^2-v-6}{10}-2,\frac{v^2-v-6}{10} $ & $ v\equiv 3 (\textsc{ mod} \; 10) $ \\ $ 3 $& $ 0,1,\ldots ,\frac{v^2-2v-8}{10}-2,\frac{v^2-2v-8}{10} $ & $ v\equiv 4,8 (\textsc{ mod} \; 10) $ \\ $ 3 \text{یا} 5 $& $ 0,1,\ldots ,\frac{v^2-2v-4}{10}-2,\frac{v^2-2v-4}{10} $ & $ v\equiv 6 (\textsc{ mod} \; 10) $ \\ $ 2 \text{یا} 4 $& $ 0,1,\ldots ,\frac{v^2-v-12}{10}-2,\frac{v^2-v-12}{10} $ & $ v\equiv 7,9( \textsc{ mod} \; 10) $ \\ \hline \end{tabular} \end{center} \caption{حل مسأله اشتراک برای ماکسیمم$-5$دور بسته بندی از $K_v$}\label{T.3} \end{table} \begin{lemma}\label{2.5.2} فرض کنید یک $ T(s_1,v_1) $ دارای یک مجموعه از $ m $ رأس مستقل وجود دارد. اگر یک $ T(s_2,v_2) $ وجود داشته باشد، آنگاه یک $ T(s_1+s_2, v_1+v_2-n) $ برای $ n=0,1, \ldots,min(m,v_2) $ وجود دارد. \end{lemma} \begin{proof} فرض کنید $ G_1 $ گراف اساسی یک $ T(s_1,v_1) $ باشد که شامل یک مجموعه از $ m $ رأس مستقل است و فرض کنید $ G_2 $ گراف اساسی یک $ T(s_2,v_2) $ باشد. $ n $ رأس از $ G_2 $ را با، $ n $ رأس مستقل $ G_1 $ یکسان درنظر میگیریم. آنگاه $G_1\cup G_2 $ گراف اساسی ترید مطلوب، $ T(s_1+s_2, v_1+v_2-n) $ است. \end{proof} \begin{lemma}\label{2.5.3} اگر $v \geq 13$ و $E(v-8)=P(v-8)$ آنگاه یک $T(s,v)$ برای تمام $s \in P(v)$ با $s \leq max(P(v-8))+2$ وجود دارد. \end{lemma} \begin{proof} لازم است که $v \geq 13$ باشد، چون باید یک ترید روی $v-8$ رأس وجود داشته باشد. دقت کنید اگر $x \in P(v)$ باشد نتیجه می‌دهد که $x \in \lbrace y+2 : y \in P(v-8) \rbrace$ یا $x> max(P(v-8))+2$ است. بنابراین لازم است تنها ببنیم که یک $T(s+2,v)$ را می‌توانیم با ترکیب یک $T(2,8)$ و $T(s,v-8)$ بسازیم. \end{proof} \begin{table}[b] \begin{center} \begin{tabular}{|c|c|} \hline $ s $ & $ v $ \\ \hline $ \frac{v^2-7v+20}{10} , \frac{v^2-7v+30}{10} , \ldots ,\frac{v^2-2v}{10}$ & $ v \equiv 0,2 ( \textsc{ mod} \; 10)$ \\ $ \frac{v^2-6v+15}{10} , \frac{v^2-6v+25}{10} , \ldots ,\frac{v^2-v}{10}$ & $ v \equiv 1,5 ( \textsc{ mod} \; 10)$ \\ $ \frac{v^2-6v+19}{10} , \frac{v^2-6v+29}{10} , \ldots ,\frac{v^2-v-6}{10}$ & $ v \equiv 3 ( \textsc{ mod} \; 10)$ \\ $ \frac{v^2-7v+22}{10} , \frac{v^2-7v+32}{10} , \ldots ,\frac{v^2-2v-8}{10}$ & $ v \equiv 4,8 (\textsc{ mod} \; 10)$ \\ $ \frac{v^2-7v+26}{10} , \frac{v^2-7v+36}{10} , \ldots ,\frac{v^2-2v-4}{10}$ & $ v \equiv 6 ( \textsc{ mod} \; 10)$ \\ $ \frac{v^2-6v+13}{10} , \frac{v^2-6v+23}{10} , \ldots ,\frac{v^2-v-12}{10}$ & $ v \equiv 7,9 (\textsc{ mod} \; 10)$ \\ \hline \end{tabular} \end{center} \caption{حجم‌های بزرگ ترید}\label{T.4} \end{table} اگر $v$ زوج باشد، آنگاه $max(P(v)) \geq \lceil \frac{v^2-2v-8}{10}\rceil$ است، و بنابراین $max(P(v-8)) \geq \lceil \frac{v^2-18v+72}{10}\rceil$ است.\\ اگر $v$ فرد باشد، $max(P(v)) \geq \lceil \frac{v^2-v-12}{10}\rceil$ ، و بنابراین $max(P(v-8)) \geq \lceil \frac{v^2-17v+60}{10}\rceil$ است.\\ بنابراین، طبق لم \ref{2.5.3} ، یک $T(s,v)$ را برای تمام مقادیر $s$ که در جدول \ref{T.5} آمده‌است را بدست می‌آوریم. \begin{table}[b] \begin{center} \begin{tabular}{|c|c|} \hline $ s $ & $ v$ \\ \hline $ \frac{v}{4},\frac{v+4}{4},\ldots ,\lceil\frac{v^2-18v+92}{10}\rceil $ & $ v \equiv 0 (\textsc{ mod} \; 8), v \geq 13 $ \\ $ \frac{v+3}{4},\frac{v+7}{4},\ldots ,\lceil\frac{v^2-17v+80}{10}\rceil $ & $ v \equiv 1,5 (\textsc{ mod} \; 8), v\geq 13 $ \\ $ \frac{v+2}{4},\frac{v+6}{4},\ldots ,\lceil\frac{v^2-18v+92}{10}\rceil $ & $ v \equiv 2,6 (\textsc{ mod} \; 8), v\geq 13 $ \\ $ \frac{v+1}{4},\frac{v+5}{4},\ldots ,\lceil\frac{v^2-17v+80}{10}\rceil $ & $ v \equiv 3,7 (\textsc{ mod} \; 8), v\geq13 $ \\ $ \frac{v+4}{4},\frac{v+8}{4},\ldots ,\lceil\frac{v^2-18v+92}{10}\rceil $ & $ v \equiv 4 (\textsc{ mod} \; 8), v\geq13 $ \\ \hline \end{tabular} \end{center} \caption{حجم‌های کوچک ترید}\label{T.5} \end{table} یک ترید جدید به سادگی می‌تواند با ترکیب دو ترید کوچک‌تر ساخته شود، چون شرطی که در یک ترید گراف اساسی باید همبند باشد وجود ندارد. لم \ref{2.5.2} همچنین نشان می‌دهد که دو ترید کوچک‌تر می‌توانند به شکل ترید بزرگ‌تر با همپوشانی روی رأس‌های مستقل در یکی از ترید‌های کوچک‌تر ترکیب شوند. فرض کنید نماد $T(s_1,v_1)+T(s_2,v_2) < x >$ یک ترکیب از ترید‌های $T(s_1,v_1)$ و $T(s_2,v_2)$ با همپوشانی روی $x$ رأس مستقل از $T(s_1,v_1)$ را نشان می‌دهد. \begin{lemma}\label{2.5.4} $E(v) = P(v)$ برای تمام $v \leq 20$. \end{lemma} \begin{proof} برای $v \leq 4$ ، $E(v)=P(v)=\emptyset $ است. برای $v=5,6,7$ در بخش تریدهایی با بنیان کوچک با شکل‌های \ref{c5,1} و \ref{c5,2} نشان دادیم که $E(v)=P(v)$ است.\\ برای $v=8$ ، $P(v)= \lbrace 2,3,4 \rbrace$ است. یک $T(2,8)$ و $T(3,8)$ در شکل \ref{c5,3} نشان داده شدند، درحالی‌که یک $T(4,8)$ طبق جدول \ref{T.4} وجود دارد.\\ برای $v=9 $ ، $P(v)=\lbrace 3,4,5,6 \rbrace$ است. یک $T(3,9)$ با شکل \ref{c5,4} داده شده‌است، \\ $T(4,9)= T(2,5)+T(2,5) < 1 >$ است، و یک $T(5,9)$ و $T(6,9)$ طبق جدول \ref{T.4} وجود دارند.\\ برای $v=10 $ ، $P(v)=\lbrace 3,4,5,6,7,8 \rbrace$ است. یک $T(3,10)$ با شکل \ref{3,10} داده شده‌است،\\ $T(4,10)= T(2,5)+T(2,5) < 0 >$ است، و یک $T(s,10)$ برای $s=5,6,7,8$ طبق جدول \ref{T.4} وجود دارند.\\ برای $v=11$ ، $P(v)=\lbrace 3,4,\ldots,11 \rbrace$ است. یک $T(3,11)$ با شکل \ref{c5,4} داده شده‌است، و \begin{flushleft} $T(4,11)= T(2,5)+T(2,6) < 0 >,$\\ $T(5,11)= T(2,5)+T(3,7) < 1 >,$\\ $T(6,11)= T(3,7)+T(3,7) < 3 >.$\\ \end{flushleft} $T(s,10)$ برای $s=7,8,9,10,11$ طبق جدول \ref{T.4} وجود دارند.\\ برای $v=12$ ، $P(v)=\lbrace4,5\ldots,12 \rbrace$ است. \begin{flushleft} $T(4,12)= T(2,6)+T(2,6) < 0 >,$\\ $T(5,12)= T(2,5)+T(3,7) < 0>,$\\ $T(6,12)= T(2,5)+T(4,8) < 1 >,$\\ $T(7,12)= T(2,7)+T(5,9) < 4 >.$\\ \end{flushleft} $T(s,12)$ برای $s=8,9,\ldots,12$ طبق جدول \ref{T.4} وجود دارند.\\ برای $v=13$ ، $P(v)=\lbrace4,5\ldots,15 \rbrace$ است. لم \ref{2.5.3} یک $T(4,13)$ را می‌دهد. \begin{flushleft} $T(5,13)= T(2,5)+T(3,8) < 0 >,$\\ $T(6,13)= T(2,5)+T(4,8) < 0 >,$\\ $T(7,13)= T(2,5)+T(5,9) < 1 >,$\\ $T(8,13)= T(2,5)+T(6,9) < 1 >,$\\ $T(9,13)= T(3,7)+T(6,9) < 3 >,$\\ $T(10,13)= T(2,7)+T(8,10) < 4 >.$ \end{flushleft} $T(s,13)$ برای $s=11,12,\ldots,15$ طبق جدول \ref{T.4} وجود دارند.\\ برای $v=14$ ، $P(v)=\lbrace4,5\ldots,16 \rbrace$ است. لم \ref{2.5.3} یک $T(4,14)$ را می‌دهد. \begin{flushleft} $T(5,14)= T(2,6)+T(3,8) < 0 >,$\\ $T(6,14)= T(2,6)+T(4,8) < 0 >,$\\ $T(7,14)= T(2,5)+T(5,9) < 0 >,$\\ $T(8,14)= T(2,5)+T(6,9) < 0 >,$\\ $T(9,14)= T(2,5)+T(7,10) < 1 >,$\\ $T(10,14)= T(2,5)+T(8,10) < 1 >,$\\ $T(11,14)= T(2,7)+T(9,11) < 4 >.$\\ \end{flushleft} $T(s,14)$ برای $s=12,13,\ldots,16$ طبق جدول \ref{T.4} وجود دارند.\\ برای $v=15$ ، $P(v)=\lbrace4,5\ldots,21 \rbrace$. لم \ref{2.5.3} ترید‌های $T(4,15)$ و $ T(5,15) $ را می‌دهد. \begin{flushleft} $T(6,15)= T(2,7)+T(4,8) < 0 >,$\\ $T(7,15)= T(2,6)+T(5,9) < 0 >,$\\ $T(8,15)= T(2,6)+T(6,9) < 0 >,$\\ $T(9,15)= T(2,5)+T(7,10) < 0 >,$\\ $T(10,15)= T(2,5)+T(8,10) < 0 >,$\\ $T(11,15)= T(2,5)+T(9,11) < 1 >,$\\ $T(12,15)= T(2,5)+T(10,11) < 1 >,$\\ $T(13,15)= T(2,5)+T(11,11) < 1 >,$\\ $T(14,15)= T(2,7)+T(12,12) < 4>.$\\ \end{flushleft} $T(s,15)$ برای $s=15,16\ldots,21$ طبق جدول \ref{T.4} وجود دارند.\\ برای $v=16 $ ، $P(v)=\lbrace4,5\ldots,22 \rbrace$ است. لم \ref{2.5.3} یک $T(4,16)$ ، یک $ T(5,16) $ ، و یک $ T(6,16) $ را می‌دهد. \begin{flushleft} $T(7,16)= T(2,7)+T(5,9) < 0 >,$\\ $T(8,16)= T(2,7)+T(6,9) < 0 >,$\\ $T(9,16)= T(2,6)+T(7,10) < 0 >,$\\ $T(10,16)= T(2,6)+T(8,10) <0>,$\\ $T(11,16)= T(2,5)+T(9,11) <0>,$\\ $T(12,16)= T(2,5)+T(10,11) < 0 >,$\\ $T(13,16)= T(2,5)+T(11,11) < 0 >,$\\ $T(14,16)= T(2,5)+T(12,12) < 1>,$\\ $T(15,16)= T(2,7)+T(13,13) < 4 >,$\\ $T(16,16)= T(2,7)+T(14,13) < 4 >.$\\ \end{flushleft} $T(s,16)$ برای $s=17,18\ldots,22$ طبق جدول \ref{T.4} وجود دارند.\\ برای $v=17 $ ، $P(v)=\lbrace 5,6 \ldots,26 \rbrace$ است. لم \ref{2.5.3} یک $T(s,17)$ را برای $s=5,6,7,8$ می‌دهد. \begin{flushleft} $T(9,17)= T(2,7)+T(7,10) < 0 >,$\\ $T(10,17)= T(2,7)+T(8,10) < 0 >,$\\ $T(11,17)= T(2,6)+T(9,11) < 0 >,$\\ $T(12,17)= T(2,6)+T(10,11) < 0 >,$\\ $T(13,17)= T(2,6)+T(11,11) < 0 >,$\\ $T(14,17)= T(2,5)+T(12,12) < 0>,$\\ $T(15,17)= T(2,5)+T(13,13) < 1 >,$\\ $T(16,17)= T(2,5)+T(14,13) < 1 >,$\\ $T(17,17)= T(2,5)+T(15,13) < 1 >,$\\ $T(18,17)= T(2,7)+T(16,14) < 4 >.$\\ \end{flushleft} یک $T(19,17)$ به شرح زیر می‌تواند ساخته شود: یک جفت $-5$ دور سیستم تقسیم‌پذیر گروهی با سه گروه از اندازه پنج و اشتراک صفر( یک $-5$ دور سیستم جزیی از گراف $K_{3(5)}$ ) یک $T(15,15)$ با سه مجموعه از پنج رأس مستقل ارائه خواهد داد؛ یک $T(2,7)$ را روی یکی از مجموعه رأس‌های مستقل بعلاوه دو رأس جدید قرار دهید تا یک $T(17,17)$ بدست آید؛ یک $T(2,5)$ را روی یک مجموعه دیگر از پنج رأس مستقل قرار دهید تا یک $T(19,17)$ بدست آید. $T(s,17)$ برای $s=20,21\ldots,26$ طبق جدول \ref{T.4} وجود دارند.\\ برای $v=18$ ، $P(v)=\lbrace5,6\ldots,82 \rbrace$ است. لم \ref{2.5.3} یک $T(s,18)$ را برای $s=5,6,\ldots ,10$ می‌دهد. \begin{flushleft} $T(11,18)= T(2,7)+T(9,11) < 0 >,$\\ $T(12,18)= T(2,7)+T(10,11) < 0 >,$\\ $T(13,18)= T(2,7)+T(11,11) < 0 >,$\\ $T(14,18)= T(2,6)+T(12,12) < 0>,$\\ $T(15,18)= T(2,5)+T(13,13) < 0 >,$\\ $T(16,18)= T(2,5)+T(14,13) < 0 >,$\\ $T(17,18)= T(2,5)+T(15,13) < 0 >,$\\ $T(18,18)= T(2,5)+T(16,14) < 1 >,$\\ $T(19,18)= T(2,7)+T(17,15) < 4 >,$\\ $T(20,18)= T(2,7)+T(18,15) < 4 >,$\\ $T(21,18)= T(2,7)+T(19,15) < 4 >.$\\ \end{flushleft} $T(s,18)$ برای $s=22\ldots,28$ طبق جدول \ref{T.4} وجود دارند.\\ برای $v=19$ ، $P(v)=\lbrace 5,6 \ldots,33 \rbrace$ است. لم \ref{2.5.3} یک $T(s,19)$ را برای $s=5,6,\ldots , 13$ می‌دهد. \begin{flushleft} $T(14,19)= T(2,7)+T(12,12) < 0>,$\\ $T(15,19)= T(2,6)+T(13,13) < 0 >,$\\ $T(16,19)= T(2,6)+T(14,13) < 0 >,$\\ $T(17,19)= T(2,6)+T(15,13) < 0 >,$\\ $T(18,19)= T(2,5)+T(16,14) < 0 >,$\\ $T(19,19)= T(2,5)+T(17,15) < 1 >,$\\ $T(20,19)= T(2,5)+T(18,15) < 1 >,$\\ $T(21,19)= T(2,5)+T(19,15) < 1 >,$\\ $T(22,19)= T(2,5)+T(20,15) < 1 >,$\\ $T(23,19)= T(2,5)+T(21,15) < 1 >,$\\ $T(24,19)= T(2,7)+T(22,16) < 4 >.$\\ \end{flushleft} یک $T(25,19)$ به شرح زیر می‌تواند ساخته شود: یک $T(15,15)$ با سه مجموعه از پنج رأس مستقل(مانند حالت $v=17$ ) درنظربگیرید؛ یک $T(6,9)$ را روی یک مجموعه از پنج رأس مستقل بعلاوه چهار رأس جدید قرار دهید تا یک $T(21,19)$ بدست آید؛ یک $T(2,5)$ را روی هر یک از مجموعه‌های باقی‌مانده از پنج رأس مستقل قرار دهید تا یک $T(25,19)$ بدست آید. $T(s,19)$ برای $s=26,27\ldots,33$ طبق جدول \ref{T.4} وجود دارند.\\ برای $v=20$ ، $P(v)=\lbrace 6,7 \ldots,36 \rbrace$ است. لم \ref{2.5.3} یک $T(s,20)$ برای $s=6,7\ldots ,14$ می‌دهد. \begin{flushleft} $T(15,20)= T(2,7)+T(13,13) < 0 >,$\\ $T(16,20)= T(2,7)+T(14,13) < 0 >,$\\ $T(17,20)= T(2,7)+T(15,13) < 0 >,$\\ $T(18,20)= T(2,6)+T(16,14) < 0 >,$\\ $T(19,20)= T(2,5)+T(17,15) < 0 >,$\\ $T(20,20)= T(2,5)+T(18,15) < 0 >,$\\ $T(21,20)= T(2,5)+T(19,15) < 0 >,$\\ $T(22,20)= T(2,5)+T(20,15) < 0 >,$\\ $T(23,20)= T(2,5)+T(21,15) < 0 >,$\\ $T(24,20)= T(2,5)+T(22,16) < 1 >,$\\ $T(25,20)= T(2,7)+T(23,17) < 4 >,$\\ $T(26,20)= T(2,7)+T(24,17) < 4 >,$\\ $T(27,20)= T(2,7)+T(25,17) < 4 >.$\\ \end{flushleft} $T(s,20)$ برای $s=28,29\ldots,36$ طبق جدول \ref{T.4} وجود دارند. \end{proof} \begin{lemma}\label{2.5.5} فرض کنید $ (G,S_1) $ و $ (G,S_2) $ یک جفت $-5 $ دور سیستم تقسیم‌پذیر گروهی با پنج گروه از اندازه $y$ باشند، و بنابراین $ \vert S_1 \vert =\vert S_2 \vert=2y^2 $ است. فرض کنید که $\vert S_1 \cap S_2 \vert=I$. (1) اگر ترید‌های $T(s_j,y)$ برای $(j=1,\ldots,5)$ ، وجود داشته‌باشند، آنگاه یک\\ $T(s_1+s_2+s_3+s_4+s_5+2y^2-I,5y) $ وجود دارد. (2) اگر $T(s_1, y+1)$ و $T(s_j,z_j)$ برای $(j=2,\ldots,5)$ وجود داشته‌باشند، که $z_j$ برابر با $y$ یا $y+1$ است، آنگاه یک $T(s_1+s_2+s_3+s_4+s_5+2y^2-I,5y+1)$ وجود دارد. (3) اگر $T(s_1, x+2) $ و $T(s_j,z_j)$ برای $(j=2,\ldots,5)$ وجود داشته‌باشند، که $z_j$ برابر با $y$ یا $y+1$ یا $y+2$ هستند و حداکثر یکی از ترید‌ها از مرتبه $y+2$ شامل هیچ زوج رأس مستقل نیست، آنگاه یک $T(s_1+s_2+s_3+s_4+s_5+2y^2-I,5y+2) $ وجود دارد. (4) اگر $T(s_1, y+3) $ و $T(s_j,z_j)$ برای $j=2,\ldots,5$ وجود داشته‌باشند، که $z_j$ برابر با $y$ یا $y+1$ یا $y+2$ یا $y+3$ است، و حداکثر یکی از ترید‌ها از مرتبه $y+2$ و $y+3$ شامل به ترتیب هیچ زوج یا هیچ سه تایی از رأس‌های مستقل نیستند، آنگاه یک $T(s_1+s_2+s_3+s_4+s_5+2y^2-I,5y+3) $ وجود دارد. (5) اگر $T(s_1, y+4) $ و $T(s_j,z_j)$ برای $(j=2,\ldots,5)$ وجود داشته‌باشند، که $z_j$ برابر با $y$ یا $y+1$ یا $y+2$ یا $y+3$ یا $y+4$ است، و حداکثر یکی از ترید‌ها از مرتبه $y+2$ ، $y+3$ و $y+4$ شامل به ترتیب هیچ زوج، یا هیچ سه تایی، یا هیچ مجموعه از چهار رأس مستقل نیستند، آنگاه یک\\ $T(s_1+s_2+s_3+s_4+s_5+2y^2-I,5y+4) $ وجود دارد. \end{lemma} \begin{proof} از لم \ref{2.5.1} استفاده می‌کنیم. اما این‌جا می‌توانیم شرط $v-d-1 > 2I$ را نادیده بگیریم چون این شرط برای اطمینان از این‌که هیچ رأس تنهایی وجود ندارد قرار داده‌شده‌بود؛ در این‌جا چون ما $-5$ دورهایی را از ترید‌هایی از حجم $s_j$ اضافه خواهیم داشت پس هیچ رأس تنهایی نخواهیم داشت. از دو $-5$ دور سیستم تقسیم‌پذیرگروهی اولیه، با استفاده از لم \ref{2.5.1} می‌توانیم فرض کنیم که یک $T(2y^2-I,5y)$ داریم که شامل پنج مجموعه‌ی مجزا از $y$ رأس مستقل است. سپس نتایج بدست آمده از لم \ref{2.5.2} را پنج بار بکار می‌بریم. \end{proof} \begin{lemma}\label{2.5.6} برای $v>20$ ، اگر $E(u)=P(u)$ برای تمام $u \leq v$ آنگاه یک $T(s,v)$ برای تمام $s$ و $v$ های داده‌شده در جدول \ref{T.6} وجود دارد.\\ \begin{table}[h] \begin{center} \begin{tabular}{|c|c|} \hline $ s $ & $ v $ \\ \hline $ 10,12,13,\ldots , 82 $&$ v=30 $ \\ $ \lceil \frac{v+30}{4} \rceil , \lceil \frac{v+34}{4} \rceil ,\ldots,\frac{v^2-2v-40}{10} $&$ v \equiv 0( \textsc{ mod} \; 10), v \geq 40$ \\ $ 10,12,13,\ldots , 42 $&$ v=21 $ \\ $ \lceil \frac{v+19}{4} \rceil , \lceil \frac{v+23}{4} \rceil ,\ldots,\frac{v^2-v-60}{10} $&$ v \equiv 1 (\textsc{ mod} \; 10), v \geq 31$ \\ $ 10,12,13,\ldots , 42 $&$ v=22 $ \\ $ \lceil \frac{v+38}{4} \rceil , \lceil \frac{v+42}{4} \rceil ,\ldots,\frac{v^2-2v-40}{10} $&$ v \equiv 2 (\textsc{ mod} \; 10), v \geq 32$ \\ $ \lceil \frac{v+33}{4} \rceil , \lceil \frac{v+37}{4} \rceil ,\ldots,\frac{v^2-4v-27}{10} $&$ v \equiv 3 (\textsc{ mod} \; 10), v \geq 23$ \\ $ 10,11,\ldots , 48 $&$ v=24 $ \\ $ \lceil \frac{v+36}{4} \rceil , \lceil \frac{v+40}{4} \rceil ,\ldots,\frac{v^2-6v-12}{10} $&$ v \equiv 4 ( \textsc{ mod} \; 10), v \geq 34$ \\ $ 10,12,13,\ldots ,60 $&$ v=25 $ \\ $ \lceil \frac{v+15}{4} \rceil , \lceil \frac{v+19}{4} \rceil ,\ldots,\frac{v^2-v-60}{10} $&$ v \equiv 5 (\textsc{ mod} \; 10), v \geq 35$ \\ $ 10,12,13,\ldots , 60 $&$ v=26 $ \\ $ \lceil \frac{v+34}{4} \rceil , \lceil \frac{v+38}{4} \rceil ,\ldots,\frac{v^2-2v-44}{10} $&$ v \equiv 6 (\textsc{ mod} \; 10), v \geq 36$ \\ $ \lceil \frac{v+23}{4} \rceil , \lceil \frac{v+27}{4} \rceil ,\ldots,\frac{v^2-v-92}{10} $&$ v \equiv 7 (\textsc{ mod} \; 10), v \geq 27$ \\ $ \lceil \frac{v+24}{4} \rceil , \lceil \frac{v+28}{4} \rceil ,\ldots,\frac{v^2-3v-80}{10} $&$ v \equiv 8 (\textsc{ mod} \; 10), v \geq 28$ \\ $ 11,12,\ldots ,68 $&$ v=29 $ \\ $ 15,16,\ldots , 133 $&$ v=39 $ \\ $ \lceil \frac{v+21}{4} \rceil , \lceil \frac{v+25}{4} \rceil ,\ldots,\frac{v^2-5v-36}{10} $&$ v \equiv 9 (\textsc{ mod} \; 10), v \geq 49$ \\ \hline \end{tabular} \end{center} \caption{حجم های متوسط ترید}\label{T.6} \end{table} \end{lemma} \begin{proof} برای اثبات ابتدا توجه می‌کنیم که، یک جفت $-5$ دور سیستم تقسیم‌پذیر گروهی با پنج گروه از اندازه $y$ وبا اشتراک‌های $\lbrace 0,1,\ldots , 2y^2-2,2y^2 \rbrace$ وجود دارد. اگر $u$ فرد و $E(u)=P(u)$ باشد، آنگاه $T(s,u)$ حداقل برای همه‌ی $s$ ها در محدوده‌ی $\lceil \frac{u}{4}\rceil , \ldots ,\lceil \frac{u^2-u-12}{10}\rceil$ وجود دارد. اگر $u$ زوج و $E(u) = P(u)$ باشد، آنگاه $T(s,u)$ حداقل برای همه‌ی $s$ ها در محدوده‌ی $\lceil \frac{u}{4}\rceil+1 , \ldots ,\lceil \frac{u^2-2u-8}{10}\rceil$ وجود دارد.\\ در هر بار یکی از حالت‌های $v \equiv 0,1,\ldots ,9 $ به پیمانه $10$ ، را درنظربگیرید.\\ \underline{$ v=10x $.} طبق لم \ref{2.5.4} تنها نیاز داریم $x \geq 3$ را در نظربگیریم.\\ اگر $x=3$ ، یک $T(s,2x)$ با $s=2$ وجود دارد و می‌توانیم این ترید را با $-5$ دور سیستم‌های تقسیم‌پذیر گروهی روی پنج گروه از اندازه $2x$ با اشتراک‌های $\lbrace 0,1,2,\ldots , 70,72 \rbrace$ ، با استفاده از قسمت (1) لم \ref{2.5.5} برای ساختن $T(10,30), T(12,30), T(13,30), \ldots ,T(82,30)$ ترکیب کنیم.\\ اگر $x \geq 4$ باشد، $T(s,2x)$ حداقل برای تمام اعداد صحیح $s$ که $\lceil \frac{ 2x}{4}\rceil +1 \leq s \leq \lceil \frac{4x^2-4x-8}{10}\rceil$ وجود دارند. بنابراین $T(s,2x)$ حداقل برای تمام اعداد صحیح $s$ که $\lceil \frac{x+2}{2}\rceil \leq s \leq \lceil \frac{2x^2-2x-4}{5}\rceil$ وجود دارند. وقتی که $x \geq 4$ باشد، این محدوده شامل حداقل دو مقدار برای $s$ است، پس از این ترید‌ها به همراه $-5$ دور سیستم‌های تقسیم‌پذیر گروهی روی پنج گروه از اندازه $2x$ با اشتراک‌های $\lbrace 0,1, \ldots ,. 8x^2-2,8x^2 \rbrace$ با استفاده از قسمت (1) لم \ref{2.5.5} ، می‌توانیم برای بدست آوردن حداقل تریدهای\\ $T(\lceil \frac{5x+15 }{2}\rceil , 10x) , \ldots ,T(2x^2-2x-4+8x^2,10x)$ استفاده کنیم. پس با اعمال شرط $ v=10x$ ترید‌های $T(\lceil \frac{v+30 }{4}\rceil ,v) , \ldots , T(\frac{v^2-2v-40}{10} ,v)$ را بدست می‌آوریم.\\ \underline{$ v=10x+1 $} طبق لم \ref{2.5.4} ، تنها نیاز داریم $x \geq 2$ را در نظربگیریم.\\ اگر $x=3$ ، یک $T(s,2x+1)$ با $s=2$ وجود دارد و می‌توانیم این ترید را با $-5$ دور سیستم‌های تقسیم‌پذیر گروهی روی پنج گروه از اندازه $2x$ با اشتراک‌های $\lbrace 0,1,2,\ldots , 30,32 \rbrace$ با استفاده از قسمت (2) لم \ref{2.5.5} برای ساختن $T(10,21), T(12,21), T(13,21), \ldots ,T(42,321)$ ترکیب کنیم.\\ اگر $x \geq 3$ ، $T(s,2x+1)$ حداقل برای تمام اعداد صحیح $s$ که $\lceil \frac{ 2x+1}{4}\rceil \leq s \leq \lceil \frac{4x^2+2x-12}{10}\rceil$ وجود دارد. بنابراین $T(s,2x+1)$ حداقل برای تمام اعداد صحیح $s$ که $\lceil \frac{x+1}{2}\rceil \leq s \leq \lceil \frac{2x^2+x-6}{5}\rceil$ وجود دارد. وقتی که $x \geq 3$ ، این محدوده شامل حداقل دو مقدار برای $s$ است، پس از این ترید‌ها به همراه $-5$ دور سیستم‌های تقسیم‌پذیر گروهی روی پنج گروه از اندازه $2x$ با اشتراک‌های $\lbrace 0,1, \ldots ,. 8x^2-2,8x^2 \rbrace$ با استفاده از قسمت (2) لم \ref{2.5.5} ، می‌توانیم برای بدست آوردن حداقل تریدهای \\ $T(\lceil \frac{5x+10 }{2}\rceil , 10x+1) , \ldots ,T(2x^2+x-6+8x^2,10x+1)$ استفاده کنیم. پس با اعمال شرط $v=10x+1$ ، ترید‌های $T(\lceil \frac{v+19 }{4}\rceil ,v) , \ldots , T(\frac{v^2-v-60}{10} ,v)$ را بدست می‌آوریم.\\ \underline{$ v=10x+2$} طبق لم \ref{2.5.4} ، تنها نیاز داریم $x \geq 2$ را در نظربگیریم.\\ اگر $x=2$ ، یک $T(s,2x+2)$ با $s=2$ وجود دارد، و یک $T(2,6)$ شامل یک زوج از رأس‌های مستقل وجود دارد. پس می‌توانیم این ترید را به همراه $-5$ دور سیستم‌های تقسیم‌پذیر گروهی روی پنج گروه از اندازه $2x$ با اشتراک‌های $\lbrace 0,1,2,\ldots , 30,32 \rbrace$ با استفاده از قسمت (3) لم \ref{2.5.5} ، برای ساختن $T(10,22), T(12,22), T(13,22), \ldots ,T(42,22)$ ترکیب کنیم.\\ اگر $x \geq 3$ ، $T(s,2x+2)$ حداقل برای تمام اعداد صحیح $s$ که $\lceil \frac{ 2x+2}{4}\rceil +1 \leq s \leq \lceil \frac{4x^2+4x-8}{10}\rceil$ وجود دارد. بنابراین $T(s,2x+2)$ حداقل برای تمام اعداد صحیح $s$ که $\lceil \frac{x+3}{2}\rceil \leq s \leq \lceil \frac{2x^2+2x-4}{5}\rceil$ وجود دارد. هر $T(s,2x+2)$ یک زوج رأس مستقل را شامل خواهد بود، زیرا $ 2x+2 $ زوج است. وقتی که $x \geq 3$ ، این محدوده شامل حداقل دو مقدار برای $s$ است، پس با این ترید‌ها به همراه $-5$ دور سیستم‌های تقسیم‌پذیر گروهی روی پنج گروه از اندازه $2x$ با اشتراک‌های $\lbrace 0,1, \ldots , 8x^2-2,8x^2 \rbrace$ در قسمت (3) لم \ref{2.5.5} ، می‌توانیم حداقل $T(\lceil \frac{5x+20 }{2}\rceil , 10x+2) , \ldots ,T(2x^2+2x-4+8x^2,10x+2)$ را بدست آوریم. پس با اعمال شرط $ v=10x+2$ ، ترید‌های $T(\lceil \frac{v+38 }{4}\rceil ,v) , \ldots , T(\frac{v^2-2v-40}{10} ,v)$ را بدست می‌آوریم.\\ \underline{$ v=10x+3 $} طبق لم \ref{2.5.4} ، تنها نیاز داریم $x \geq 2$ را در نظربگیریم.\\ اگر $x \geq 2$ ، $T(s,2x+3)$ حداقل برای تمام اعداد صحیح $s$ که $\lceil \frac{ 2x+3}{4}\rceil \leq s \leq \lceil \frac{4x^2+10x-6}{10}\rceil$ وجود دارد. بنابراین $T(s,2x+3)$ حداقل برای تمام اعداد صحیح $s$ که $\lceil \frac{x+2}{2}\rceil \leq s \leq \lceil \frac{2x^2+5x-3}{5}\rceil$ وجود دارند. وقتی که $x \geq 2$ ، این محدوده شامل حداقل دو مقدار برای $s$ است.اما، نمی‌توانیم تضمین کنیم که این ترید‌ها شامل سه رأس مستقل خواهند بود، پس ترید‌های مطلوب را با استفاده از یک $T(s,2x+2)$ که می‌دانیم شامل زوج‌ رأس‌های مستقل است چون $2x+2 $ زوج است، خواهیم ساخت. بنابراین با بکار بردن قسمت (4) لم \ref{2.5.5} و با یک ترید روی $ 2x+3 $ رأس و چهار ترید روی $ 2x+2$ رأس، به همراه $-5$ دور سیستم‌های تقسیم‌پذیر گروهی روی پنج گروه از اندازه $2x$ با اشتراک‌های $\lbrace 0,1, \ldots , 8x^2-2,8x^2 \rbrace$ ، کوچکترین حجم تریدی که می‌توانیم بسازیم (با $ I=8x^2 $ ) $ \lceil \frac{x+2}{2}\rceil +4\lceil \frac{x+3}{2}\rceil $ است، و بزرگترین حجم تریدی که می‌توانیم بسازیم (با $ I=0 $ )، $ \lceil \frac{2x^2+5x-3}{5}\rceil +4\lceil \frac{2x^2+2x-4}{5}\rceil +8x^2 $ است. با ساده کردن این عبارت‌ها حداقل تریدهای $T(\lceil \frac{5x+18 }{2}\rceil , 10x+3) , \ldots ,T(\frac{100x^2+20x-30}{10},10x+3)$. را بدست می‌آوریم. پس با استفاده از شرط $ v=10x+3 $ ، ترید‌های $T(\lceil \frac{v+33 }{4}\rceil ,v) , \ldots , T(\frac{v^2-4v-27}{10} ,v)$ را بدست می‌آوریم.\\ \underline{$ v=10x+4$} طبق لم \ref{2.5.4} ، تنها نیاز داریم $x \geq 2$ را در نظربگیریم.\\ اگر $x=2$ ، $T(s,2x+4)$ برای $s= \lbrace 2,3,4 \rbrace $ وجود دارد. اما، این ترید‌ها هر یک شامل مجموعه‌ای از چهار رأس مستقل نیستند. برای $x=2$ ، $T(s,2x+3)$ برای $s= \lbrace 2,3\rbrace $ هریک شامل مجموعه‌ای از سه رأس مستقل وجود دارد. بنابراین، با استفاده از قسمت (5) لم \ref{2.5.5} با یک ترید روی $ 2x+4 $ رأس و چهار ترید روی $ 2x+3$ رأس، به همراه $-5$ دور سیستم‌های تقسیم‌پذیر گروهی روی پنج گروه از اندازه $2x$ با اشتراک‌های $\lbrace 0,1,2,\ldots , 30,32 \rbrace$ ، ترید‌های $T(10,24), \ldots ,T(48,24)$ را بدست می‌آوریم.\\ اگر $x \geq 3$ ، $T(s,2x+4)$ حداقل برای تمام اعداد صحیح $s$ که $\lceil \frac{ 2x+4}{4}\rceil +1 \leq s \leq \lceil \frac{4x^2+12x}{10}\rceil$ وجود دارد. بنابراین $T(s,2x+4)$ حداقل برای تمام اعداد صحیح $s$ که $\lceil \frac{x+4}{2}\rceil \leq s \leq \lceil \frac{2x^2+6x}{5}\rceil$ وجود دارد، و این محدوده شامل حداقل دو مقدار برای $s$ است. اما، نمی‌توانیم تضمین کنیم که این ترید‌ها شامل چهار رأس مستقل خواهند بود پس ترید‌ها را با استفاده از یک $T(s,2x+2)$ ، که می‌دانیم شامل زوج‌ رأس‌های مستقل است چون $2x+2 $ زوج است خواهیم ساخت. بنابراین با بکار بردن قسمت (5) لم \ref{2.5.5} و با یک ترید روی $ 2x+4 $ رأس و چهار ترید روی $ 2x+2$ رأس، به همراه $-5$ دور سیستم‌های تقسیم‌پذیر گروهی روی پنج گروه از اندازه $2x$ با اشتراک‌های $\lbrace 0,1, \ldots ,8x^2-2,8x^2 \rbrace$ ، کوچکترین حجم تریدی که می‌توانیم بسازیم (با $ I=8x^2 $ ) $ \lceil \frac{x+4}{2}\rceil +4\lceil \frac{x+3}{2}\rceil $ است، و بزرگترین حجم تریدی که می‌توانیم بسازیم (با $ I=0 $ ) $ \lceil \frac{2x^2+6x}{5}\rceil +4\lceil \frac{2x^2+2x-4}{5}\rceil +8x^2 $ است.با ساده کردن این عبارت‌ها، حداقل تریدهای $T(\lceil \frac{5x+20 }{2}\rceil , 10x+4) , \ldots ,T(\frac{100x^2+20x-20}{10},10x+4)$. را بدست می‌آوریم. پس با استفاده از شرط $ v=10x+4$ ، ترید‌های $T(\lceil \frac{v+36 }{4}\rceil ,v) , \ldots , T(\frac{v^2-6v-1}{10} ,v)$ را بدست می‌آوریم.\\ \underline{$ v=10x+5$} طبق لم \ref{2.5.4} ، تنها نیاز داریم $x \geq 2$ را در نظربگیریم.\\ اگر $x=2$ ، یک $T(s,2x+1)$ با $s=2$ وجود دارد، و می‌توانیم این ترید را با $-5$ دور سیستم‌های تقسیم‌پذیر گروهی روی پنج گروه از اندازه $2x+1$ با اشتراک‌های $\lbrace 0,1,2,\ldots , 48,50 \rbrace$ ، با استفاده از قسمت (1) لم \ref{2.5.5} برای ساختن $T(10,21), T(12,21), T(13,21), \ldots ,T(60,21)$ ، ترکیب کنیم.\\ اگر $x \geq 3$ ، $T(s,2x+1)$ حداقل برای تمام اعداد صحیح $s$ که $\lceil \frac{ 2x+1}{4}\rceil \leq s \leq \lceil \frac{4x^2+2x-12}{10}\rceil$ وجود دارد. بنابراین $T(s,2x+1)$ حداقل برای تمام اعداد صحیح $s$ که $\lceil \frac{x+1}{2}\rceil \leq s \leq \lceil \frac{2x^2+x-6}{5}\rceil$ وجود دارد. وقتی که $x \geq 3$ ، این محدوده شامل حداقل دو مقدار برای $s$ است، پس از این ترید‌ها به همراه $-5$ دور سیستم‌های تقسیم‌پذیر گروهی روی پنج گروه از اندازه $2x+1$ با اشتراک‌های\\ $\lbrace 0,1, \ldots ,8x^2+8x,8x^2+8x+2 \rbrace$ در قسمت(1) لم \ref{2.5.5} ، می‌توانیم برای بدست آوردن حداقل $T(\lceil \frac{5x+100 }{2}\rceil , 10x+5) , \ldots ,T(2x^2+x-6+8x^2+8x+2,10x+5)$ استفاده کنیم. پس با استفاده از شرط $ v=10x+5$ ترید‌های $T(\lceil \frac{v+15 }{4}\rceil ,v) , \ldots , T(\frac{v^2-v-60}{10} ,v)$ را بدست می‌آوریم.\\ \underline{$ v=10x+6$} طبق لم \ref{2.5.4} ، تنها نیاز داریم $x \geq 2$ را در نظربگیریم.\\ اگر $x=2$ ، یک $T(s,2x+2)$ با $s=2$ و می‌توانیم این ترید را با $-5$ دور سیستم‌های تقسیم‌پذیر گروهی روی پنج گروه از اندازه $2x+1$ با اشتراک‌های $\lbrace 0,1,2,\ldots , 48,50 \rbrace$ با استفاده از قسمت (2) لم \ref{2.5.5} برای ساختن $T(10,26), T(12,26), T(13,26), \ldots ,T(60,26)$ ترکیب کنیم .\\ اگر $x \geq 3$ ، $T(s,2x+2)$ حداقل برای تمام اعداد صحیح $s$ که $\lceil \frac{ 2x+2}{4}\rceil \leq s \leq \lceil \frac{4x^2+4x-8}{10}\rceil$ وجود دارد. بنابراین $T(s,2x+2)$ حداقل برای تمام اعداد صحیح $s$ که $\lceil \frac{x+3}{2}\rceil \leq s \leq \lceil \frac{2x^2+2x-4}{5}\rceil$ وجود دارد. وقتی‌که $x \geq 3$ ، این محدوده شامل حداقل دو مقدار برای $s$ است، پس با این ترید‌ها به همراه $-5$ دور سیستم‌های تقسیم‌پذیر گروهی روی پنج گروه از اندازه $2x+1$ با اشتراک‌های\\ $\lbrace 0,1, \ldots ,8x^2+8x,8x^2+8x+2 \rbrace$ ، در قسمت (2) لم \ref{2.5.5} ، می‌توانیم حداقل تریدهای\\ $T(\lceil \frac{5x+20 }{2}\rceil , 10x+6) , \ldots ,T(2x^2+2x-4+8x^2+8x+2,10x+6)$ را بدست آوریم. پس با استفاده از شرط $ v=10x+6$ ترید‌های $T(\lceil \frac{v+34}{4}\rceil ,v) , \ldots , T(\frac{v^2-2v-44}{10} ,v)$ را بدست می‌آوریم.\\ \underline{$ v=10x+7 $} طبق لم \ref{2.5.4} ، تنها نیاز داریم $x \geq 2$ را در نظربگیریم.\\ اگر $x \geq 2$ ، $T(s,2x+3)$ حداقل برای تمام اعداد صحیح $s$ که $\lceil \frac{ 2x+3}{4}\rceil \leq s \leq \lceil \frac{4x^2+10x-6}{10}\rceil$ وجود دارد. بنابراین $T(s,2x+3)$ حداقل برای تمام اعداد صحیح $s$ که $\lceil \frac{x+2}{2}\rceil \leq s \leq \lceil \frac{2x^2+5x-3}{5}\rceil$ وجود دارد. وقتی که $x \geq 2$ ، این محدوده شامل حداقل دو مقدار برای $s$ است. نمی‌توانیم تضمین کنیم که این ترید‌ها شامل یک جفت از رأس‌های مستقل خواهند بود، اما یک ترید روی $ 2x+3 $ رأس شامل یک جفت از رأس‌های مستقل خواهد بود به شرط این‌که از بیشترین حجم نباشد. بنابراین می‌توانیم قسمت (3) لم \ref{2.5.5} را با یک ترید روی $ 2x+3 $ رأس که مجاز است به داشتن هر حجمی، و چهار ترید روی $ 2x+3$ رأس که مجاز است به داشتن هر حجمی به‌جز بیشترین حجم ممکن، به همراه $-5$ دور سیستم‌های تقسیم‌پذیر گروهی روی پنج گروه از اندازه $2x+1$ با اشتراک‌های $\lbrace 0,1, \ldots ,8x^2+8x-2,8x^2+8x+2 \rbrace$ ، بکار ببریم. حال با بکار بردن قسمت (3) لم \ref{2.5.5} ، کوچکترین حجم تریدی که می‌توانیم بسازیم (با $ I=8x^2+8x+2 $ )، $ 5\lceil \frac{x+2}{2}\rceil$ است و بزرگترین حجم تریدی که می‌توانیم بسازیم (با $ I=0 $ )، $ \lceil \frac{2x^2+5x-3}{5}\rceil +4( \lceil \frac{2x^2+5x-3}{5}\rceil -1)+8x^2+8x+2$ است. با ساده کردن این عبارت‌ها، حداقل تریدهای $T(\lceil \frac{5x+15 }{2}\rceil , 10x+7) , \ldots ,T(10x^2+13x-5,10x+7)$. را بدست می‌آوریم. پس با استفاده از شرط $ v=10x+7 $ ، ترید‌های $T(\lceil \frac{v+23 }{4}\rceil ,v) , \ldots , T(\frac{v^2-v-92}{10} ,v)$ را بدست می‌آوریم.\\ \underline{$ v=10x+8 $} طبق لم \ref{2.5.4} ، تنها نیاز داریم $x \geq 2$ را در نظربگیریم.\\ اگر $x \geq 2$ ، $T(s,2x+4)$ حداقل برای تمام اعداد صحیح $s$ که $\lceil \frac{ 2x+4}{4}\rceil+1 \leq s \leq \lceil \frac{4x^2+12x}{10}\rceil$ وجود دارد. بنابراین $T(s,2x+4)$ حداقل برای تمام اعداد صحیح $s$ که $\lceil \frac{x+4}{2}\rceil \leq s \leq \lceil \frac{2x^2+6x}{5}\rceil$ وجود دارد. وقتی‌که $x \geq 2$ ، این محدوده شامل حداقل دو مقدار برای $s$ است. نمی‌توانیم تضمین کنیم که این ترید‌ها شامل یک مجموعه از سه رأس مستقل خواهند بود، اما یک ترید روی $ 2x+3 $ رأس شامل یک جفت از رأس‌های مستقل خواهد بود، به شرط اینکه از بیشترین حجم نباشد. بنابراین می‌توانیم قسمت (4) لم \ref{2.5.5} را با یک ترید روی $ 2x+4 $ رأس که مجاز است به داشتن هر حجمی و چهار ترید روی $ 2x+3$ رأس که مجاز است به داشتن هر حجمی به‌جز بیشترین حجم ممکن، به همراه $-5$ دور سیستم‌های تقسیم‌پذیر گروهی روی پنج گروه از اندازه $2x+1$ با اشتراک‌های $\lbrace 0,1, \ldots ,8x^x+8x-2,8x^2+8x+2 \rbrace$ ، بکار ببریم. حال با بکار بردن قسمت (4) لم \ref{2.5.5} ، کوچکترین حجم تریدی که می‌توانیم بسازیم (با $ I=8x^2+8x+2 $ )، $ \lceil \frac{x+4}{2}\rceil+4\lceil \frac{x+2}{2}\rceil$ است و بزرگترین حجم تریدی که می‌توانیم بسازیم (با $ I=0 $ )، $ \lceil \frac{2x^2+6x}{5}\rceil +4( \lceil \frac{2x^2+5x-3}{5}\rceil -1)+8x^2+8x+2$ است. با ساده کردن این عبارت‌ها حداقل تریدهای $T(\lceil \frac{5x+16 }{2}\rceil , 10x+8) , \ldots ,T(\frac{100x^2+130x-40}{10},10x+8)$. را بدست می‌آوریم. پس با استفاده از شرط $ v=10x+8$ ، ترید‌های $T(\lceil \frac{v+24 }{4}\rceil ,v) , \ldots , T(\frac{v^2-3v-80}{10} ,v)$ را بدست می‌آوریم.\\ \underline{$ v=10x+9$} طبق لم \ref{2.5.4} ، تنها نیاز داریم $x \geq 2$ را در نظربگیریم.\\ اگر $x=2$ ، $T(s,2x+5)$ برای $s= \lbrace 3,4,5,6 \rbrace $ وجود دارد. اما، این ترید‌ها هر یک شامل مجموعه ای از چهار رأس مستقل نیستند. برای $x=2$ ، $T(s,2x+3)$ برای $s= \lbrace 2,3\rbrace $ که هر یک شامل مجموعه ای از سه رأس مستقل هستند، وجود دارد. بنابراین، با استفاده از قسمت (5) لم \ref{2.5.5} با یک ترید روی $ 2x+5 $ رأس و چهار ترید روی $ 2x+3$ رأس، به همراه $-5$ دور سیستم‌های تقسیم‌پذیر گروهی روی پنج گروه از اندازه $2x+1$ با اشتراک‌های $\lbrace 0,1,2,\ldots , 48,50 \rbrace$ ، ترید‌های $T(11,29), \ldots ,T(68,29)$ رابدست می‌آوریم.\\ اگر $x=3$ ، $T(s,2x+5)$ برای $s= \lbrace 3,4,\ldots, 11 \rbrace $ وجود دارد. اما، این ترید‌ها هر یک شامل مجموعه ای از چهار رأس مستقل نیستند. برای $x=3$ ، $T(s,2x+3)$ برای $s= \lbrace 3,4,5,6\rbrace $ که هریک شامل مجموعه ای از سه رأس مستقل است، وجود دارد. بنابراین، با استفاده از قسمت (5) لم \ref{2.5.5} با یک ترید روی $ 2x+5 $ رأس و چهار ترید روی $ 2x+3$ رأس، به همراه $-5$ دور سیستم‌های تقسیم‌پذیر گروهی روی پنج گروه از اندازه $2x+1$ با اشتراک‌های $\lbrace 0,1,\ldots , 96,98\rbrace$ ، ترید‌های $T(15,39), \ldots ,T(133,39)$ رابدست می‌آوریم.\\ اگر $x \geq 4$ ، $T(s,2x+5)$ حداقل برای تمام اعداد صحیح $s$ که $\lceil \frac{ 2x+5}{4}\rceil \leq s \leq \lceil \frac{4x^2+18x+8}{10}\rceil$ وجود دارد. بنابراین $T(s,2x+5)$ حداقل برای تمام اعداد صحیح $s$ که $\lceil \frac{x+3}{2}\rceil \leq s \leq \lceil \frac{2x^2+9x+4}{5}\rceil$ وجود دارد، و این محدوده شامل حداقل دو مقدار برای $s$ است. اما، نمی‌توانیم تضمین کنیم که این ترید‌ها شامل چهار رأس مستقل باشند، اما یک ترید روی $ 2x+3 $ رأس شامل یک جفت از رأس‌های مستقل خواهد بود، به شرط این‌که از بیشترین حجم نباشد. بنابراین می‌توانیم قسمت(5) لم \ref{2.5.5} را با یک ترید روی $ 2x+5 $ رأس که مجاز است به داشتن هر حجمی و چهار ترید روی $ 2x+3$ رأس که مجاز است به داشتن هر حجمی به جز بیشترین حجم ممکن، به همراه $-5$ دور سیستم‌های تقسیم‌پذیر گروهی روی پنج گروه از اندازه $2x+1$ با اشتراک‌های $\lbrace 0,1, \ldots ,8x^2+8x,8x^2+8x+2 \rbrace$ بکار ببریم. حال با بکار بردن قسمت(5) لم \ref{2.5.5} ، کوچکترین حجم تریدی که می‌توانیم بسازیم (با $ I=8x^2+8x+2 $ )، $ \lceil \frac{x+3}{2}\rceil+4\lceil \frac{x+2}{2}\rceil$ است و بزرگترین حجم تریدی که می‌توانیم بسازیم (با $ I=0 $ )، $ \lceil \frac{2x^2+9x+4}{5}\rceil +4( \lceil \frac{2x^2+5x-3}{5}\rceil -1)+8x^2+8x+2$ است. با ساده کردن این عبارت‌ها، حداقل تریدهای $T(\lceil \frac{5x+15 }{2}\rceil , 10x+9) , \ldots ,T(\frac{100x^2+130x}{10},10x+9)$. را بدست می‌آوریم. پس با استفاده از شرط $v=10x+9$ ، ترید‌های $T(\lceil \frac{v+21 }{4}\rceil ,v) , \ldots , T(\frac{v^2-5v-36}{10} ,v)$ را بدست می‌آوریم.\\ \end{proof} \begin{theorem} برای تمام اعداد صحیح نامنفی $v$ ، $E(v)=P(v)$. \end{theorem} \begin{proof} طبق لم \ref{2.5.4} ، اگر $v \leq 20$ ، آنگاه نتیجه برقراراست. برای $ v > 20 $ ، با درنظرگرفتن هریک از مقادیر $ v $ به پیمانه‌ی $ 10 $ قضیه را ثابت خواهیم کرد. باید بررسی کنیم که حجم ترید‌های داده‌شده در جدول‌های \ref{T.4} ، \ref{T.5} و \ref{T.6} با هم تمام حجم ترید‌های ممکن( یعنی مجموعه $P(v)$ ) را می‌پوشانند. برای مثال $ v \equiv 1 $ به پیمانه‌ی $10$ را درنظربگیرید.\\ اگر $ v=21 $ ، $ P(v) = \lbrace 6,7, \ldots , 42 \rbrace $ است. جدول \ref{T.4} حجم‌های $33, 34, \ldots, 42$ را می‌دهد، جدول \ref{T.6} حجم‌های $ 10, 12, 13, \ldots, 42$ را می‌دهد و جدول \ref{T.5} حجم‌های $6, 7, \ldots, 17$ را می‌دهد.\\ اگر $ v \geq 31 $ ، $P(v) = \lbrace \lceil \frac{v}{4} \rceil, \ldots , \frac{v^2-v}{10} \rbrace$ است. جدول \ref{T.4} حجم‌های $ \frac{v^2-6v-15}{10} \leq s \leq \frac{v^2-v}{10} $ را می‌دهد، جدول \ref{T.6} حجم‌های $\lceil \frac{v+19}{4}\rceil \leq s \leq \frac{v^2-v-60}{10} $ را می‌دهد و جدول \ref{T.5} حجم‌های\\ $\lceil \frac{v}{4}\rceil \leq s \leq \lceil \frac{v^2-17v+80}{10}\rceil $ را می‌دهد. جدول‌های \ref{T.4} و \ref{T.6} برای $ v \geq 15 $ ، تمام حجم‌های ممکن را می‌پوشانند و جدول‌های \ref{T.6} و \ref{T.5} برای $ v \geq 18 $ ، تمام حجم‌های ممکن را می‌پوشانند. پس واضح است که برای $ v > 20 $ و $ v \equiv 1$ به پیمانه‌ی $ 10 $ تمام مقادیر ممکن $ s $ بدست آمده‌است.\\ بررسی این‌که نتیجه برای دیگر رده‌های همنهشتی نیز برقرار است، به سادگی و به صورت مشابه است. \end{proof} \section{طیف $ -C_6 $ترید } در این بخش حجم‌های ترید مجاز برای یک بنیان $v$ داده شده را برای گراف $C_6$ بدست می‌آوریم. \begin{theorem}\label{61.1} شرط‌های لازم و کافی برای وجود $C_6$ ترید از بنیان $v$ و حجم $s$ ، این است که $v \geq 6$ و $m(v) \leq s \leq M(v)$ ، که \begin{equation*} m(v)= \left\{ \begin{array}{rl} \lceil \frac{v}{5}\rceil & \;v \not\equiv 5\;(\textsc{ mod} \;10) \text{اگر }\\ \frac{v}{5}+1 &\;v \equiv 5 \;(\textsc{ mod} \;10) \text{اگر }\\ \end{array} \right. \end{equation*} \begin{equation*} M(v)= \left\{ \begin{array}{rl} \frac{v^2 -2v}{12} & v \equiv 0,2 \;(\textsc{ mod} \;6) \text{اگر }\\ \frac{v^2 -2v-8}{12} & v \equiv 4 \;(\textsc{ mod} \;6) \text{اگر }\\ \frac{v^2 -v}{12} & v \equiv 1,9 \;(\textsc{ mod} \;12) \text{اگر }\\ \frac{v^2 -v-6}{12} &\;v \equiv 3,7 \;(\textsc{ mod} \;12) \text{اگر } \\ \frac{v^2 -v-8}{12} &\;v \equiv 5\;(\textsc{ mod} \;12) \text{اگر } \\ \frac{v^2 -v-14}{12} & ~~v \equiv 11 \;(\textsc{ mod} \;12)\text{اگر }\\ \end{array} \right. \end{equation*} \end{theorem} اثبات لزوم به سادگی است زیرا: با استفاده از نتایج ماکسیمم $-6$ دور بسته بندی از \cite{6max} داریم $s \leq M(v)$ . زیرا برای یک ترید داده شده از بنیان $v$ ، مثلاً $\lbrace T_1 , T_2 \rbrace$ ، هر یک از $T_1$ و $T_2$ یک بسته بندی از $K_v$ با کپی‌هایی از $C_6$ است، و تمام $v$ رأس در بلوک‌های $T_1$ و بلوک‌های $T_2$ واقع می‌شوند.\\ همچنین کران پایین $C_6$ ترید‌ها از قسمت دوم قضیه \ref{61.2} بدست می‌آید. در ادامه کفایت قضیه را نشان می‌دهیم. \subsection{حالت‌های کوچک} تعدادی از $C_6$ ترید‌های کوچک که کفایت قضیه \ref{61.1} را برای $v \in \lbrace 6,7,8,9,10,11,12,13,15,17 \rbrace$ ثابت می‌کند و برای ساختار‌های بخش بعد مورد نیاز هستند را می‌سازیم که در پیوست \eqref{c6} آمده‌اند. \subsection{ساختار اصلی} در این بخش کفایت شرط‌های قضیه \ref{61.1} را برای ترید‌هایی از همه بنیان‌های باقی‌مانده $v$ ثابت می‌کنیم. با نتیجه‌ای برای ترید‌های روی گراف‌های دوبخشی شروع می‌کنیم. که در ساختار لم‌های \ref{64.2} و \ref{64.3} به آن نیاز داریم. توجه کنید که ترید‌هایی از حجم کمتر از یک سوم بنیان به طور جداگانه در اثبات قضیه \ref{6.4.1}. ساخته شده‌اند. \begin{lemma}\label{64.1} برای هر عدد صحیح زوج $v$ $(v \geq 4)$ ، و هر $s$ زوج $(0 \leq s \leq v)$ ، یک ترید از حجم $s$ که فقط یال‌های گراف دو بخشی $K_{v,6}$ را استفاده می‌کند وجود دارد (این ترید لزوماً همه یال‌ها یا همه رأس‌های $K_{v,6}$ را استفاده نخواهد کرد). \end{lemma} \begin{proof} مجموعه رأس‌های $V$ و $U$ را درنظربگیرید، که $\vert V \vert =v$ و $\vert U \vert =6$ . مجموعه رأس $V$ می‌تواند به زیر مجموعه‌هایی از اندازه $4$ یا $6$ افراز شود، و بنابراین گراف $K_{v,6}$ با مجموعه رأس $V \cup U$ می‌تواند به کپی‌هایی از $K_{4,6}$ و $K_{6,6}$ تجزیه شود. روی هر کپی از $K_{4,6}$ می‌توانیم $T(2;K_{4,4})$ یا $T(4;K_{4,6})$ را قرار دهیم. روی هرکپی از $K_{6,6}$ می‌توانیم $T(2;K_{4,4})$ ، $T(4;K_{4,6})$ یا $T(6;K_{6,6})$ را قرار دهیم(که این ترید‌ها در پیوست \eqref{c6} آمده‌اند). ترکیب این ترید‌ها یک ترید از هر حجم زوج تا $v$ را به ما خواهد داد. \end{proof} \begin{lemma}\label{64.2} برای هر $v$ زوج $(v \geq 8)$ ، اگر ترید‌های $T(\lfloor v/3\rfloor,\ldots ,M(v) ;v)$ وجود داشته‌باشند، آنگاه ترید‌های $T(\lfloor( v+6)/3\rfloor,\ldots ,M(v+6) ;v+6)$ وجود دارند. \end{lemma} \begin{proof} مجموعه رأس‌های $V$ و $U$ که $\vert V \vert =v$ و $\vert U \vert =6$ را درنظربگیرید. طبق فرض می‌توانیم ترید‌هایی از هر حجمی بین $\lfloor v/3\rfloor$ تا $M(v)$ را روی $V$ قرار دهیم، که تمام رأس‌های $V$ را استفاده کنند، و می‌توانیم یک ترید از حجم $2$ روی $U$ قرار دهیم، که تمام رأس‌های $U$ را استفاده کند. طبق لم \ref{64.1} همچنین می‌توانیم یک ترید از هر حجم زوج به بالا تا $v$ ، را روی یک گراف دوبخشی کامل روی رأس‌های $V \cup U$ قرار دهیم. از تعریف $M(v)$ به آسانی برای $v \geq 8$ داریم $M(v)- \lfloor v/3\rfloor \geq 1$ ، و بنابراین ترکیب این ترید‌ها یک ترید از بنیان $v+6$ و هر حجمی از $\lfloor (v+6)/3\rfloor$ تا $M(v) +v+2$ را به ما می‌دهد. چون $v$ زوج است و $v \geq 8$ ، از تعریف نتیجه می‌شود که $M(v)+v+2=M(v+6)$ ، پس نتیجه بدست می‌آید. \end{proof} \begin{lemma}\label{64.3} برای هر $v$ فرد، $v \geq 7$ ، اگر ترید‌های $T(\lfloor v/3\rfloor,\ldots ,M(v) ;v)$ وجود داشته‌باشند، آنگاه ترید‌های $T(\lfloor (v+12)/3\rfloor,\ldots ,M(v+12) ;v+12)$ وجود دارند. \end{lemma} \begin{proof} مجموعه رأس‌های $W$ ، $U$ و $\lbrace \infty \rbrace$ ، که $\vert W \vert = v-1$ و $\vert U \vert =12$ است، را درنظربگیرید. طبق فرض می‌توانیم یک ترید از هر حجمی از $\lfloor (v/3)\rfloor$ تا $M(v)$ را روی $W \cup \lbrace \infty\rbrace$ قرار دهیم، که تمام رأس‌های $W \cup \lbrace \infty\rbrace$ را استفاده می‌کند، و می‌توانیم یک ترید از هر حجمی از $3$ تا $13$ روی $U \cup \lbrace \infty\rbrace$ قراردهیم، که تمام رأس‌های $U \cup \lbrace \infty\rbrace$ را استفاده می‌کند( یکی از ترید‌های $T(3,4,\ldots,13;13)$ را استفاده می‌کنیم). گراف کامل دو بخشی تشکیل شده از $W$ و $U$ به سادگی به دو کپی از $K_{v-1,6}$ تجزیه می‌شود، و بنابراین طبق لم \ref{64.1} می‌توانیم یک ترید از هر حجم زوج به بالا تا $2(v-1)$ را نیز روی این گراف قرار دهیم. ترکیب این ترید‌ها یک ترید از بنیان $v+12$ و هر حجمی از $\lfloor v/3\rfloor+3$ تا $M(v)+2(v-1)+13$ را به ما می‌دهد. حال $\lfloor v/3\rfloor+3 \leq \lfloor (v+12)/3\rfloor$ است، و چون $v$ فرد است و $v \geq 7$ ، از تعریف نتیجه می‌شود که $M(v)+2(v-1)+13=M(v+12)$ ، پس نتیجه بدست می‌آید. \end{proof} \begin{theorem}\label{6.4.1} برای هر عدد صحیح $v \geq 6$ ، ترید‌های $ T(\lfloor v/3\rfloor,\ldots ,M(v) ;v) $ وجود دارد. \end{theorem} \begin{proof} با استفاده از تریدهایی که در پیوست \eqref{c6} آمده است، می‌دانیم که قضیه برای \\ $v \in \lbrace 6,7,8,9,10,11,12,13,15,17\rbrace$ برقرار است. با استفاده از لم‌های \ref{64.2} و \ref{64.3} ، نتیجه به صورت استقرایی برای تمام $v \geq 6$ دیگر بدست می‌آید. \end{proof} \begin{theorem} برای هر عدد صحیح $v \geq 6$ ، ترید‌های $T( m(v),\ldots,\lfloor v/3\rfloor ;v)$ وجود دارد. \end{theorem} \begin{proof} فرض کنید $m(v) \leq s \leq \lfloor v/3\rfloor$ . اگر $s$ زوج باشد آنگاه $v/5 \leq s \leq v/3$ ، و بنابراین $3s \leq v \leq 5s$ . یک ترید از حجم $s$ را از اجتماع مجزایی از $s/2$ ترید از حجم $2$ تشکیل می‌دهیم. هر یک از این تریدها می‌توانند هر بنیانی از $6$ تا $10$ داشته‌باشند، و بنابراین ترید ترکیبی هر بنیانی از $3s$ تا $5s$ دارد. اگر $s$ فرد باشد داریم $(v+1)/5 \leq s \leq v/3$ ، و بنابراین $3s \leq v \leq 5s-1$ . یک ترید از حجم $s$ را از اجتماع مجزایی از $(s-3)/2$ ترید از حجم $2$ و یک ترید از حجم $3$ تشکیل می‌دهیم. هر ترید از حجم $2$ می‌تواند هر بنیانی از $6$ تا $10$ داشته باشد در حالی که ترید از حجم $3$ می‌تواند هر بنیانی از $7$ تا $14$ داشته باشد. بنابراین ترید ترکیبی می‌تواند هر بنیانی از $3s-2$ تا $5s-1$ داشته باشد. \end{proof}