The question. The following problem appears as exercise 2.1.75 in Doug West's "Introduction to Graph Theory" (2nd edition) and as exercise 3.8 in Chartrand and Lesniak's "Graphs & Digraphs" (3rd edition) (and almost certainly in other elementary graph theory textbooks, unbeknownst to me):
Let $T$ be a tree of order $n$ other than $K_{1, n-1}$. Prove that $T \subseteq \overline{T}$.
Relevant definitions. I think everything here is standard, but just in case: A tree is a graph which is connected and acyclic. The bipartite graph $K_{1, n-1}$ is sometimes referred to as a "star," and hence a "non-star tree" of order $n$ is any tree other than $K_{1, n-1}$. Given any graph $G$, denote by $\overline{G}$ its complement; that is, the graph on the same vertex set as $G$ which has an edge present between a pair of vertices exactly when $G$ does not. A subgraph $H$ of a given graph $G$ is such that $V(H) \subseteq V(G)$, $E(H) \subseteq E(G)$, and the assignment of endpoints to edges in $H$ is the same as in $G$. A $(p, q)$ graph is any graph of order $p$ and size $q$ (i.e. a graph with $p$ vertices and $q$ edges).
Why I care about this problem. The reason I'm interested in this problem is that I'm working through all of the "interesting" (in my opinion) exercises from Doug West's book (self-paced, though I've taken graph theory courses at university before some years ago). This problem is particularly striking because it is so simple/short to state and understand, yet its proof is difficult (at least for me). I also was not able to find a solution on this site (or from googling other sources).
Some more context. Doug West's book gives the following hint for this exercise:
Hint: Proceeding by induction on $n$, prove the following stronger statement: If $T$ is a non-star tree of order $n$, then $K_n$ contains two edge-disjoint copies of $T$ in which the two copies of each non-leaf vertex of $T$ appear at distinct vertices.
Moreover, West gives a reference for this problem:
Burns D. and S. Schuster. "Embedding $(p, p-1)$ graphs in their complements." Israel J. Math. 30 (1978), 313-320.
Unfortunately the only places I found this article online were paywalled.
My attempted proof, following West's hint. Following the hint, we prove (using induction on $n$) that if $T$ is a non-star tree of order $n$, then $K_n$ contains two edge-disjoint copies of $T$ in which the two copies of each non-leaf vertex of $T$ appear at distinct vertices.
Basis: By simple checking, we see that the only non-star tree of order $\leq 4$ is $P_4$, which is self-complementary. Hence the statement holds for all trees of order $\leq 4$.
Induction Hypothesis: Suppose that for any non-star tree $T$ of order $k = 5, 6, …, n-1$, $K_k$ contains two edge-disjoint copies of $T$ in which the two copies of each non-leaf vertex of $T$ appear at distinct vertices.
Inductive Step: Now let $T$ be a non-star tree of order $n > 4$. In the spirit of induction, we'd like to find some vertex (or vertices) to delete which leave a non-star tree of smaller order. Since we're working with trees, the natural attempt would be to find a leaf (or leaves) to delete. A way to distinguish non-star trees from stars is that stars do not contain paths of length $> 2$, while non-star trees (of order $> 4$) always do (this is pretty easy to see). Hence take a longest path in $T$; both endpoints are leaves. If the longest path in $T$ is $T$ itself (i.e. $T = P_n$), pick either leaf; otherwise, pick any leaf in $T$ which is not an endpoint of the longest path (this third leaf must exist if $T \neq P_n$; again, this is pretty easy to see). In either case, $T$ will still have a path of length $> 2$, and hence we have found a leaf (say $v$) in $T$ which, upon deletion, leaves another non-star tree $T' = T – v$ of order $n – 1$.
Let $w$ be the neighbor of $v$ in $T$. If $w$ is not a leaf in $T'$, then the Induction Hypothesis immediately gives two edge-disjoint copies of $T'$ in $K_{n – 1}$ in which $w$ occurs at distinct vertices (of $K_{n – 1}$). By placing $v$ as the new vertex added to form $K_n$, it's easy to see we can extend the two copies of $T'$ into copies of $T$ while satisfying the hypotheses of our statement. Hence we may assume that $w$ is a leaf of $T'$.
I feel pretty good up to this point, but am quite shaky on how to proceed. Of course, we need only consider when the copies of $w$ (now assumed to be a leaf in $T'$) in $K_{n – 1}$ are the same (if they're different, we can just proceed as above). I'm guessing that the way to proceed is by analysing the other neighbors of $w$ (besides $v$) and trying to use the Induction Hypothesis to get somewhere, but I haven't been able to find the right course yet.
My (updated) request. I'm perfectly fine with either hints or full solutions, whatever is easier for the potential writer. Below, you'll see that @bof has knowledgeably provided what I see as a correct verification of the truth of the statement; however, the argument is slightly case-intensive and somewhat "mathematically inelegant" (if you're a mathematician (in particular a graph-theorist), you'll know what I mean by this). If you're wanting to contribute further to this question, I'd very much appreciate one of the following:
- Prove the statement using West's hint/method, either carrying on from where I left off or starting from the beginning yourself, or
- Disregard West's hint and prove the statement "directly and cleanly," i.e. avoiding as much tedious case-work as possible, perhaps even avoiding induction altogether.
Best Answer
Here's an inductive proof not following the hint. (It's not a better way to do the exercise, just different. It's the first thing that occurred to me after reading the problem without looking at the hint. The hinted-at proof seems to be more elegant, and proves a stronger result.)
Let $T$ be a tree of order $n$ which is not a star. Choose two vertices $x,y$ of $T$ with $d(x,y)=\operatorname{diam}(T)\gt2$, so that $x$ and $y$ are leaves, and let $S=T-x-y$, a tree of order $n-2$. The leaves $x,y$ are joined to two distinct vertices $u,v$ of $S$.
Case 1. If $S$ is not a star, then by the inductive hypothesis there are two edge-disjoint isomorphic copies of $S$, call them $S'$ and $S''$, on the same vertex set $V$. We may assume that $x,y\notin V$. Let $W=V\cup\{x,y\}$. Let $u',v'$ and $u'',v''$ be the vertices corresponding to $u,v$ in $S'$ and $S''$.
Case 1a. If $u'\ne u''$ and $v'\ne v''$, then $S'+xu'+yv'$ and $S''+xu''+yv''$ are edge-disjoint copies of $T$ on the vertex set $W$.
Case 1b. If $u'=u''$ or $v'=v''$, then $u'\ne v''$ and $v'\ne u''$, so $S'+xu'+yv'$ and $S''+yu''+xv''$ are edge-disjoint copies of $T$ on the vertex set $W$.
Case 2. If $S$ is a star, then the inductive hypothesis doesn't apply. In this case we may assume that either $T=P_5$ or else $T-v$ is a star; for if $d(u,v)=4$ and $T$ is not a path, then there is a leaf $w$ such that $d(u,w)=3$, so $T-u-w$ is not a star and we can proceed as in Case 1.
Case 2a. If $T=P_5$, simply observe that $P_5$ is a spanning subgraph of the self-complementary graph $C_5$.
Case 2b. Suppose $T-v=K_{1,n}$ where $n\ge2$. Say $T$ has vertices $v,x,y_1,y_2,\dots,y_n$ and edges $xy_1,xy_2,\dots,xy_n,vy_1$. An edge-disjoint copy of $T$ on the same vertex set has edges $vx,vy_2,\dots,vy_n,y_1y_2$.