IsCaterpillarTree(G) returns true if G is a caterpillar tree and false otherwise.

IsLobsterTree(G) returns true if G is a lobster tree and false otherwise.

A graph G is a caterpillar tree if it is a tree and there exists a path in G such that every vertex in G is either on the path or adjacent to a vertex on the path.

A graph G is a lobster tree if it is a tree and the result of removing all leaf #nodes of G is a caterpillar tree.

$\mathrm{with}\left(\mathrm{GraphTheory}\right)\:$

$\mathrm{G1}≔\mathrm{Graph}\left(9\,\left\{\left\{1\,4\right\}\,\left\{2\,4\right\}\,\left\{3\,4\right\}\,\left\{4\,5\right\}\,\left\{5\,6\right\}\,\left\{6\,7\right\}\,\left\{7\,8\right\}\,\left\{7\,9\right\}\right\}\right)$

$\mathrm{G1}≔\mathrm{Graph\; 1:\; an\; undirected\; graph\; with\; 9\; vertices\; and\; 8\; edges}$

$\mathrm{DrawGraph}\left(\mathrm{G1}\,\mathrm{style}=\mathrm{planar}\right)$

$\mathrm{IsCaterpillarTree}\left(\mathrm{G1}\right)$

$\mathrm{true}$

$\mathrm{IsLobsterTree}\left(\mathrm{G1}\right)$

$\mathrm{true}$

$\mathrm{G2}≔\mathrm{Graph}\left(9\,\left\{\left\{1\,2\right\}\,\left\{2\,3\right\}\,\left\{3\,4\right\}\,\left\{3\,6\right\}\,\left\{3\,8\right\}\,\left\{4\,5\right\}\,\left\{6\,7\right\}\,\left\{8\,9\right\}\right\}\right)$

$\mathrm{G2}≔\mathrm{Graph\; 2:\; an\; undirected\; graph\; with\; 9\; vertices\; and\; 8\; edges}$

$\mathrm{DrawGraph}\left(\mathrm{G2}\,\mathrm{style}=\mathrm{planar}\right)$

$\mathrm{IsCaterpillarTree}\left(\mathrm{G2}\right)$

$\mathrm{false}$

$\mathrm{IsLobsterTree}\left(\mathrm{G2}\right)$

$\mathrm{true}$

$\mathrm{G3}≔\mathrm{GraphUnion}\left(\mathrm{PathGraph}\left(7\right)\,\mathrm{PathGraph}\left(\left[4\,8\,9\,10\right]\right)\right)$

$\mathrm{G3}≔\mathrm{Graph\; 3:\; an\; undirected\; graph\; with\; 10\; vertices\; and\; 9\; edges}$

$\mathrm{DrawGraph}\left(\mathrm{G3}\,\mathrm{style}=\mathrm{spring}\right)$

$\mathrm{IsTree}\left(\mathrm{G3}\right)$

$\mathrm{true}$

$\mathrm{IsLobsterTree}\left(\mathrm{G3}\right)$

$\mathrm{false}$

The GraphTheory[IsCaterpillarTree] and GraphTheory[IsLobsterTree] commands were introduced in Maple 2025.

For more information on Maple 2025 changes, see Updates in Maple 2025.