3-trees with diameter 2

Proof. A $k$-tree $G$ has diameter at most 2 if and only if the distance between any two vertices of $G$ is at most 2. By Lemma 2.2, this will be the case if and only if any two $k$-leaves are at distance at most 2. This will hold if and only if any two $k$-leaves of $G$ have a common neighbor. 

Proof. $(\Rightarrow )$ Any $k$-tree $T$ has a deletion sequence $v_1\cdots v_n$ so that $d\left(v_i\right)=max\{k,n-i\}$ when $v_i$ is deleted. Joining a vertex $x$ to $T$ results in a graph $T^{\prime }$ with a deletion sequence $v_1\cdots v_{n}x$ so that $d\left(v_i\right)=max\{k+1,n+1-i\}$ when $v_i$ is deleted. Thus $T^{\prime }$ is a ($k+1$)-tree.

$(\Leftarrow )$ Let $T+K_1$ have the $K_1$ denoted $x$. Then $T+K_1$ has a deletion sequence $v_1\cdots v_{n}x$ so that $d\left(v_i\right)=max\{k+1,n+1-i\}$ when $v_i$ is deleted. Thus $T$ has a deletion sequence $v_1\cdots v_n$ so that $d\left(v_i\right)=max\{k,n-i\}$ when $v_i$ is deleted, so $T$ is a $k$-tree.

The proof for $k$-paths is essentially the same. 

Proof. $(\Leftarrow )$ If $T$ has a dominating triple, then there is a path of length at most 3 between any two vertices of $T$.

$(\Rightarrow )$ Suppose that $T$ has diameter at most 3. The result is obvious for diameter 1 or 2, so suppose $T$ has diameter 3.

We use induction on $n$. Assume the result holds for 2-trees with order $n$, and let $T$ have order $n+1$, and 2-leaf $v$. Now $T-v$ has diameter at most 3, so it has a dominating triple $t=\{x,y,z\}$. If $v$ is adjacent to any of its vertices, $T$ also has a dominating triple and we are done. Thus we assume that $T$ has no dominating triple with a vertex adjacent to $v$.

Deleting two vertices of $t$ (say $x$ and $y$) will disconnect $v$ from the third ($z$). Thus there is a vertex $w$ adjacent to $x$ and $y$ in the same component of $T-x-y$ as $v$. We may assume that $z$ has no private neighbor $a$, since else $d(v,a)=4$. But then $\{x,y,w\}$ is also a dominating triple. Thus by our assumption, $v$ is not adjacent to $w$. Say $d(v,x)=2$. Then $y$ has no private neighbor $b$, since else $d(v,b)=4$. But then $x$ is a dominating vertex of $T-v$. Let $N\left(v\right)=\{u_1,u_2\}$. Then $T$ has a dominating triple $\{x,u_1,u_2\}$. 

Proof. $(\Leftarrow )$ If this holds, any vertex of $T$ is adjacent to a vertex of $t$.

$(\Rightarrow )$ Let $T$ have a dominating triple $t=\{x,y,z\}$. Let $v$ be a vertex not in $t$, so $v$ is adjacent to a vertex $x$ of $t$. If $v$ is adjacent to two vertices of $t$, it is contained in a fan centered at $x$. Else $v$ is adjacent to $x$ and a vertex $u$ not in $t$. Now $u$ is adjacent to $x$, and the argument can be repeated, producing a fan centered at $x$. 

Proof. $(\Leftarrow )$ Clearly each construction produces a 3-tree. In Case 1, there is a dominating vertex. In Case 2, every pair of vertices not in $\{u,x,y,z\}$ has a neighbor in $\{u,x,y,z\}$. In Case 3, every pair of vertices not in $\{u,x,y\}$ has a neighbor in $\{u,x,y\}$. Thus each 3-tree has diameter at most 2.

$(\Rightarrow )$ Assume the hypotheses. Let $u$ have maximum degree in $T$, $S=V\left(T\right)-N\left[u\right]$, and $H=N\left(u\right)$. Now $H$ is a 2-tree [7], so $T-S$ is a 3-tree. Thus if $u$ is a dominating vertex, $T-u$ is a 2-tree by Lemma 2.5. Thus we assume $T$ has no dominating vertex, so $S$ is nonempty.

Clearly, every vertex in $S$ neighbors a vertex in $H$. Let $R$ be all vertices in $H$ with neighbors in $S$. Every vertex in $R$ is contained in a triangle of $H$, and each pair of these triangles must have a have a nonempty intersection, since else two vertices of $S$ have no common neighbor. Then $R$ is a union of triangles, and the graph induced by $R$ has diameter 2. It is contained in a minimal 2-tree $T^{\prime }$ which has diameter 2, so by Proposition 1.3, $T^{\prime }$ has a dominating vertex or a common triple.

Suppose $T^{\prime }$ has a dominating vertex $x$. Now $H$ must have diameter 2, since else some vertex in $S$ would be more than 2 away from a vertex in $H$. If $x$ is dominating in $H$, $x$ is also dominating in $T$. By assumption, we can exclude this case. Thus $H$ has a common triple, so $T^{\prime }$ does also.

Next we assume that $T^{\prime }=K_3$, whose vertices are $\{x,y,z\}$, none of which is dominating in $H$. There is at least one vertex $v$ in $S$ whose neighbors are $T^{\prime }$. Then any other vertex in $H$ is adjacent to a vertex in $T^{\prime }$ and $u$. Then $T$ is formed by fan overlapping with bases $ux$, $uy$, or $xy$, and adding at least one 3-leaf with root $\{x,y,z\}$.

Next we assume that $T^{\prime }=K_2+{\overline{K}}_s$, the vertices of $K_2$ are $\{x,y\}$, neither of which is dominating in $H$. Then for each vertex $w$ in the ${\overline{K}}_s$, there is at least one vertex in $S$ not adjacent to it (else we return to the previous case). Then every vertex of $T$ not in $D=\{u,x,y\}$ is adjacent to at least two vertices in $D$. Thus every vertex not in $D$ is part of a 3-fan with base $ux$, $uy$, or $xy$, and there is at least one vertex of $T$ adjacent to all vertices of $D$.

Finally, we assume $T^{\prime }$ contains a triangle $xyz$, any other vertex of $T^{\prime }$ is adjacent to exactly two of $\{x,y,z\}$, and each pair ($xy$, $xz$, and $yz$) has at least one additional neighbor in $T^{\prime }$. Now each vertex of $T^{\prime }$ is adjacent to at least one vertex in $S$, so $H=T^{\prime }$. Thus each vertex in $S$ is adjacent to at least two vertices in $\{x,y,z\}$. Thus each vertex in $T$ is adjacent to at least two vertices in $\{x,y,z\}$. But then we can return to the previous case by giving $\{x,y,z\}$ the roles of $\{u,x,y\}$. 

Proof. In Case 1, a 3-tree with a dominating vertex has $\mathrm{\Delta }=n-1$, so $n=\mathrm{\Delta }+1$.

In Case 2, for each vertex $v\in \{u,x,y,z\}$, let $S_v$ be the set of vertices not adjacent to $v$. To have $\mathrm{\Delta }\left(T\right)=n-1-r$, each $S_v$ must contain at least $r$ vertices. Now vertices in $S_u$ are adjacent to triangle $xyz$, so they are only in $S_u$.

The vertices in $S_x$ may be in $S_y$ or $S_z$ (not both), and similarly for the vertices in $S_y$ or $S_z$. However, there must be at least one vertex only in one of the sets $S_x$, $S_y$, or $S_z$. If there is exactly one vertex adjacent to (say) $\{u,y,z\}$, then $\mathrm{\Delta }\left(T\right)=n-1-r$ requires at least $r$ vertices each in $S_y$ and $S_z$, and none in both. Thus $n\ge 4+3r+1=3r+5$ and $\mathrm{\Delta }\left(T\right)\ge n-1-\frac{n-5}{3}=\frac{2}{3}n+\frac{2}{3}$, so $n\le \frac{3\mathrm{\Delta }-2}{2}$.

Suppose there are two vertices in only one of the sets $S_x$, $S_y$, or $S_z$, say one each in sets $S_x$ and $S_y$. Any other vertex can be in any two of the three sets. Then $s$ vertices in $S_x\cup S_y\cup S_z$ yield $\left|S_x\right|\cup \left|S_y\right|\cup \left|S_z\right|\le 2s-2$, so $r\le \frac{2s-2}{3}$. Now $n=4+s+r\ge 4+\frac{3r+2}{2}+r=\frac{5r+10}{2}$, so $r\le \frac{2n-10}{5}$. Then $\mathrm{\Delta }\left(T\right)\ge n-1-\frac{2n-10}{5}=\frac{3n}{5}+1$. Thus $n\le \frac{5\mathrm{\Delta }-5}{3}$.

In Case 3, $K_3+{\overline{K}}_r$ has $r\ge 1$, with $uxy$ being the $K_3$. There are at most $n-4$ vertices with exactly two neighbors in $K_3+{\overline{K}}_r$. These vertices split into three sets based on which of $\{u,x,y\}$ they are not adjacent to. When $\mathrm{\Delta }$ is minimum, one of these sets contains at least $\frac{n-4}{3}$ vertices. Then $\mathrm{\Delta }\ge n-1-\frac{n-4}{3}=\frac{2n+1}{3}$, so $n\le \frac{3\mathrm{\Delta }-1}{2}$. 

Proof. In Case 1, for $T$ to be planar, $H$ must be outerplanar.

In Cases 2 and 3, for $T$ to be planar, it must be a simple 3-tree, so each root is used at most once. Thus each triangle of $K_4$ or $K_3+{\overline{K}}_r$ can be used at most once for overlapping, and no other triangle can be used for overlapping. In Case 3, $r\le 2$, since $K_3+{\overline{K}}_3$ is not planar. 

Proof. In Case 1, a 3-tree with a dominating vertex has $\mathrm{\Delta }=n-1$, so $n=\mathrm{\Delta }+1$.

In Case 2, there can only be one vertex not adjacent to $u$, so $\mathrm{\Delta }\ge n-2$, and $n\le \mathrm{\Delta }+2$.

In Case 3, $K_3+{\overline{K}}_r$ has $1\le r\le 2$, with $uxy$ being the $K_3$. There are at most $n-4$ vertices with exactly two neighbors in $K_3+{\overline{K}}_r$. These vertices split into three sets based on which of $\{u,x,y\}$ they are not adjacent to. When $\mathrm{\Delta }$ is minimum, one of these sets contains at least $\frac{n-4}{3}$ vertices. Then $\mathrm{\Delta }\ge n-1-\frac{n-4}{3}=\frac{2n+1}{3}$, so $n\le \frac{3\mathrm{\Delta }-1}{2}$.