Wolfram Function Repository
Instant-use add-on functions for the Wolfram Language
Function Repository Resource:
Caterpillar
Test whether a Tree has a path that is within one edge of every vertex
Contributed by:
Jon McLoone
Details
In graph theory, a caterpillar tree is a tree that has a path that passes within one edge of every vertex. This means that every vertex not on the path has an edge connecting it to a vertex on the path.
Examples
Basic Examples (2)
Every vertex of this tree is within one edge of a spine path from vertex 1 to vertex 8:
| In[1]:= | ![ResourceFunction["CaterpillarTreeQ"][\!\(\*
GraphicsBox[
NamespaceBox["Trees",
DynamicModuleBox[{Typeset`tree = HoldComplete[
Tree[1, {
Tree[2, {
Tree[3, None],
Tree[4, None],
Tree[5, {
Tree[6, {
Tree[7, {
Tree[8, None],
Tree[9, None]}]}]}]}]}]]},
NamespaceBox[{
{Hue[0.6, 0.7, 0.7], Opacity[0.7], CapForm["Round"], Arrowheads[
Medium],
{RGBColor[0.6, 0.5882352941176471, 0.5529411764705883], AbsoluteThickness[1], LineBox[{{0.8728715609439696, 4.200773815108915}, {
0.8728715609439696, 3.3606190520871326`}}]},
{RGBColor[0.6, 0.5882352941176471, 0.5529411764705883], AbsoluteThickness[1], LineBox[{{0.8728715609439696, 3.3606190520871326`}, {0., 2.5204642890653495`}}]},
{RGBColor[0.6, 0.5882352941176471, 0.5529411764705883], AbsoluteThickness[1], LineBox[{{0.8728715609439696, 3.3606190520871326`}, {
0.8728715609439696, 2.5204642890653495`}}]},
{RGBColor[0.6, 0.5882352941176471, 0.5529411764705883], AbsoluteThickness[1], LineBox[{{0.8728715609439696, 3.3606190520871326`}, {
1.7457431218879391`, 2.5204642890653495`}}]},
{RGBColor[0.6, 0.5882352941176471, 0.5529411764705883], AbsoluteThickness[1], LineBox[{{1.7457431218879391`, 2.5204642890653495`}, {
1.7457431218879391`, 1.6803095260435663`}}]},
{RGBColor[0.6, 0.5882352941176471, 0.5529411764705883], AbsoluteThickness[1], LineBox[{{1.7457431218879391`, 1.6803095260435663`}, {
1.7457431218879391`, 0.8401547630217834}}]},
{RGBColor[0.6, 0.5882352941176471, 0.5529411764705883], AbsoluteThickness[1], LineBox[{{1.7457431218879391`, 0.8401547630217834}, {
1.3093073414159544`, 0.}}]},
{RGBColor[0.6, 0.5882352941176471, 0.5529411764705883], AbsoluteThickness[1], LineBox[{{1.7457431218879391`, 0.8401547630217834}, {
2.182178902359924, 0.}}]}},
{Hue[0.6, 0.5, 1.], EdgeForm[{GrayLevel[0], Opacity[0.7]}],
TagBox[InsetBox[
FrameBox["1",
Background->Directive[
RGBColor[0.9607843137254902, 0.9882352941176471, 0.9764705882352941]],
BaseStyle->GrayLevel[0],
FrameMargins->{{2, 2}, {1, 1}},
FrameStyle->Directive[
RGBColor[0.4196078431372549, 0.6313725490196078, 0.4196078431372549], AbsoluteThickness[1],
Opacity[1]],
ImageSize->Automatic,
RoundingRadius->4,
StripOnInput->False], {0.8728715609439696, 4.200773815108915}],
"DynamicName",
BoxID -> "VertexID$1"],
TagBox[InsetBox[
FrameBox["2",
Background->Directive[
RGBColor[0.9607843137254902, 0.9882352941176471, 0.9764705882352941]],
BaseStyle->GrayLevel[0],
FrameMargins->{{2, 2}, {1, 1}},
FrameStyle->Directive[
RGBColor[0.4196078431372549, 0.6313725490196078, 0.4196078431372549], AbsoluteThickness[1],
Opacity[1]],
ImageSize->Automatic,
RoundingRadius->4,
StripOnInput->False], {0.8728715609439696, 3.3606190520871326}],
"DynamicName",
BoxID -> "VertexID$2"],
TagBox[InsetBox[
FrameBox["3",
Background->Directive[
RGBColor[0.9607843137254902, 0.9882352941176471, 0.9764705882352941]],
BaseStyle->GrayLevel[0],
FrameMargins->{{2, 2}, {1, 1}},
FrameStyle->Directive[
RGBColor[0.4196078431372549, 0.6313725490196078, 0.4196078431372549], AbsoluteThickness[1],
Opacity[1]],
ImageSize->Automatic,
RoundingRadius->0,
StripOnInput->False], {0., 2.5204642890653495}],
"DynamicName",
BoxID -> "VertexID$3"],
TagBox[InsetBox[
FrameBox["4",
Background->Directive[
RGBColor[0.9607843137254902, 0.9882352941176471, 0.9764705882352941]],
BaseStyle->GrayLevel[0],
FrameMargins->{{2, 2}, {1, 1}},
FrameStyle->Directive[
RGBColor[0.4196078431372549, 0.6313725490196078, 0.4196078431372549], AbsoluteThickness[1],
Opacity[1]],
ImageSize->Automatic,
RoundingRadius->0,
StripOnInput->False], {0.8728715609439696, 2.5204642890653495}],
"DynamicName",
BoxID -> "VertexID$4"],
TagBox[InsetBox[
FrameBox["5",
Background->Directive[
RGBColor[0.9607843137254902, 0.9882352941176471, 0.9764705882352941]],
BaseStyle->GrayLevel[0],
FrameMargins->{{2, 2}, {1, 1}},
FrameStyle->Directive[
RGBColor[0.4196078431372549, 0.6313725490196078, 0.4196078431372549], AbsoluteThickness[1],
Opacity[1]],
ImageSize->Automatic,
RoundingRadius->4,
StripOnInput->False], {1.7457431218879391, 2.5204642890653495}],
"DynamicName",
BoxID -> "VertexID$5"],
TagBox[InsetBox[
FrameBox["6",
Background->Directive[
RGBColor[0.9607843137254902, 0.9882352941176471, 0.9764705882352941]],
BaseStyle->GrayLevel[0],
FrameMargins->{{2, 2}, {1, 1}},
FrameStyle->Directive[
RGBColor[0.4196078431372549, 0.6313725490196078, 0.4196078431372549], AbsoluteThickness[1],
Opacity[1]],
ImageSize->Automatic,
RoundingRadius->4,
StripOnInput->False], {1.7457431218879391, 1.6803095260435663}],
"DynamicName",
BoxID -> "VertexID$6"],
TagBox[InsetBox[
FrameBox["7",
Background->Directive[
RGBColor[0.9607843137254902, 0.9882352941176471, 0.9764705882352941]],
BaseStyle->GrayLevel[0],
FrameMargins->{{2, 2}, {1, 1}},
FrameStyle->Directive[
RGBColor[0.4196078431372549, 0.6313725490196078, 0.4196078431372549], AbsoluteThickness[1],
Opacity[1]],
ImageSize->Automatic,
RoundingRadius->4,
StripOnInput->False], {1.7457431218879391, 0.8401547630217834}],
"DynamicName",
BoxID -> "VertexID$7"],
TagBox[InsetBox[
FrameBox["8",
Background->Directive[
RGBColor[0.9607843137254902, 0.9882352941176471, 0.9764705882352941]],
BaseStyle->GrayLevel[0],
FrameMargins->{{2, 2}, {1, 1}},
FrameStyle->Directive[
RGBColor[0.4196078431372549, 0.6313725490196078, 0.4196078431372549], AbsoluteThickness[1],
Opacity[1]],
ImageSize->Automatic,
RoundingRadius->0,
StripOnInput->False], {1.3093073414159544, 0.}],
"DynamicName",
BoxID -> "VertexID$8"],
TagBox[InsetBox[
FrameBox["9",
Background->Directive[
RGBColor[0.9607843137254902, 0.9882352941176471, 0.9764705882352941]],
BaseStyle->GrayLevel[0],
FrameMargins->{{2, 2}, {1, 1}},
FrameStyle->Directive[
RGBColor[0.4196078431372549, 0.6313725490196078, 0.4196078431372549], AbsoluteThickness[1],
Opacity[1]],
ImageSize->Automatic,
RoundingRadius->0,
StripOnInput->False], {2.182178902359924, 0.}],
"DynamicName",
BoxID -> "VertexID$9"]}}]]],
AlignmentPoint->Center,
Axes->False,
AxesLabel->None,
AxesOrigin->Automatic,
AxesStyle->{},
Background->None,
BaseStyle->{},
BaselinePosition->Automatic,
ContentSelectable->Automatic,
DefaultBaseStyle->"TreeGraphics",
DisplayFunction->Identity,
Epilog->{},
FormatType->StandardForm,
Frame->False,
FrameLabel->None,
FrameStyle->{},
FrameTicks->None,
FrameTicksStyle->{},
GridLines->None,
GridLinesStyle->{},
ImageMargins->0.,
ImagePadding->All,
ImageSize->{124.99923225170994`, Automatic},
LabelStyle->{},
PlotLabel->None,
PlotRange->All,
PlotRangeClipping->False,
PlotRangePadding->Automatic,
PlotRegion->Automatic,
Prolog->{},
RotateLabel->True,
Ticks->Automatic,
TicksStyle->{}]\)]](https://www.wolframcloud.com/obj/resourcesystem/images/d41/d418c154-0208-4834-bfa2-4ad22869cd9f/6d63f1fcef995d06.png) |
| Out[1]= |  |
Here vertex 10 is not within one edge of the spine path:
| In[2]:= | ![ResourceFunction["CaterpillarTreeQ"][\!\(\*
GraphicsBox[
NamespaceBox["Trees",
DynamicModuleBox[{Typeset`tree = HoldComplete[
Tree[1, {
Tree[2, {
Tree[3, {
Tree[10, None]}],
Tree[4, None],
Tree[5, {
Tree[6, {
Tree[7, {
Tree[8, None],
Tree[9, None]}]}]}]}]}]]},
NamespaceBox[{
{Hue[0.6, 0.7, 0.7], Opacity[0.7], CapForm["Round"], Arrowheads[
Medium],
{RGBColor[0.6, 0.5882352941176471, 0.5529411764705883], AbsoluteThickness[1], LineBox[{{0.8846517369293828, 4.257771773343896}, {
0.8846517369293828, 3.4062174186751166`}}]},
{RGBColor[0.6, 0.5882352941176471, 0.5529411764705883], AbsoluteThickness[1], LineBox[{{0.8846517369293828, 3.4062174186751166`}, {0., 2.5546630640063377`}}]},
{RGBColor[0.6, 0.5882352941176471, 0.5529411764705883], AbsoluteThickness[1], LineBox[{{0.8846517369293828, 3.4062174186751166`}, {
0.8846517369293828, 2.5546630640063377`}}]},
{RGBColor[0.6, 0.5882352941176471, 0.5529411764705883], AbsoluteThickness[1], LineBox[{{0.8846517369293828, 3.4062174186751166`}, {
1.7693034738587656`, 2.5546630640063377`}}]},
{RGBColor[0.6, 0.5882352941176471, 0.5529411764705883], AbsoluteThickness[1], LineBox[{{0., 2.5546630640063377`}, {0., 1.703108709337558}}]},
{RGBColor[0.6, 0.5882352941176471, 0.5529411764705883], AbsoluteThickness[1], LineBox[{{1.7693034738587656`, 2.5546630640063377`}, {
1.7693034738587656`, 1.703108709337558}}]},
{RGBColor[0.6, 0.5882352941176471, 0.5529411764705883], AbsoluteThickness[1], LineBox[{{1.7693034738587656`, 1.703108709337558}, {
1.7693034738587656`, 0.851554354668779}}]},
{RGBColor[0.6, 0.5882352941176471, 0.5529411764705883], AbsoluteThickness[1], LineBox[{{1.7693034738587656`, 0.851554354668779}, {
1.3269776053940743`, 0.}}]},
{RGBColor[0.6, 0.5882352941176471, 0.5529411764705883], AbsoluteThickness[1], LineBox[{{1.7693034738587656`, 0.851554354668779}, {
2.211629342323457, 0.}}]}},
{Hue[0.6, 0.5, 1.], EdgeForm[{GrayLevel[0], Opacity[0.7]}],
TagBox[InsetBox[
FrameBox["1",
Background->Directive[
RGBColor[0.9607843137254902, 0.9882352941176471, 0.9764705882352941]],
BaseStyle->GrayLevel[0],
FrameMargins->{{2, 2}, {1, 1}},
FrameStyle->Directive[
RGBColor[0.4196078431372549, 0.6313725490196078, 0.4196078431372549], AbsoluteThickness[1],
Opacity[1]],
ImageSize->Automatic,
RoundingRadius->4,
StripOnInput->False], {0.8846517369293828, 4.257771773343896}],
"DynamicName",
BoxID -> "VertexID$1"],
TagBox[InsetBox[
FrameBox["2",
Background->Directive[
RGBColor[0.9607843137254902, 0.9882352941176471, 0.9764705882352941]],
BaseStyle->GrayLevel[0],
FrameMargins->{{2, 2}, {1, 1}},
FrameStyle->Directive[
RGBColor[0.4196078431372549, 0.6313725490196078, 0.4196078431372549], AbsoluteThickness[1],
Opacity[1]],
ImageSize->Automatic,
RoundingRadius->4,
StripOnInput->False], {0.8846517369293828, 3.4062174186751166}],
"DynamicName",
BoxID -> "VertexID$2"],
TagBox[InsetBox[
FrameBox["3",
Background->Directive[
RGBColor[0.9607843137254902, 0.9882352941176471, 0.9764705882352941]],
BaseStyle->GrayLevel[0],
FrameMargins->{{2, 2}, {1, 1}},
FrameStyle->Directive[
RGBColor[0.4196078431372549, 0.6313725490196078, 0.4196078431372549], AbsoluteThickness[1],
Opacity[1]],
ImageSize->Automatic,
RoundingRadius->4,
StripOnInput->False], {0., 2.5546630640063377}],
"DynamicName",
BoxID -> "VertexID$3"],
TagBox[InsetBox[
FrameBox["10",
Background->Directive[
RGBColor[0.9607843137254902, 0.9882352941176471, 0.9764705882352941]],
BaseStyle->GrayLevel[0],
FrameMargins->{{2, 2}, {1, 1}},
FrameStyle->Directive[
RGBColor[0.4196078431372549, 0.6313725490196078, 0.4196078431372549], AbsoluteThickness[1],
Opacity[1]],
ImageSize->Automatic,
RoundingRadius->0,
StripOnInput->False], {0., 1.703108709337558}],
"DynamicName",
BoxID -> "VertexID$4"],
TagBox[InsetBox[
FrameBox["4",
Background->Directive[
RGBColor[0.9607843137254902, 0.9882352941176471, 0.9764705882352941]],
BaseStyle->GrayLevel[0],
FrameMargins->{{2, 2}, {1, 1}},
FrameStyle->Directive[
RGBColor[0.4196078431372549, 0.6313725490196078, 0.4196078431372549], AbsoluteThickness[1],
Opacity[1]],
ImageSize->Automatic,
RoundingRadius->0,
StripOnInput->False], {0.8846517369293828, 2.5546630640063377}],
"DynamicName",
BoxID -> "VertexID$5"],
TagBox[InsetBox[
FrameBox["5",
Background->Directive[
RGBColor[0.9607843137254902, 0.9882352941176471, 0.9764705882352941]],
BaseStyle->GrayLevel[0],
FrameMargins->{{2, 2}, {1, 1}},
FrameStyle->Directive[
RGBColor[0.4196078431372549, 0.6313725490196078, 0.4196078431372549], AbsoluteThickness[1],
Opacity[1]],
ImageSize->Automatic,
RoundingRadius->4,
StripOnInput->False], {1.7693034738587656, 2.5546630640063377}],
"DynamicName",
BoxID -> "VertexID$6"],
TagBox[InsetBox[
FrameBox["6",
Background->Directive[
RGBColor[0.9607843137254902, 0.9882352941176471, 0.9764705882352941]],
BaseStyle->GrayLevel[0],
FrameMargins->{{2, 2}, {1, 1}},
FrameStyle->Directive[
RGBColor[0.4196078431372549, 0.6313725490196078, 0.4196078431372549], AbsoluteThickness[1],
Opacity[1]],
ImageSize->Automatic,
RoundingRadius->4,
StripOnInput->False], {1.7693034738587656, 1.703108709337558}],
"DynamicName",
BoxID -> "VertexID$7"],
TagBox[InsetBox[
FrameBox["7",
Background->Directive[
RGBColor[0.9607843137254902, 0.9882352941176471, 0.9764705882352941]],
BaseStyle->GrayLevel[0],
FrameMargins->{{2, 2}, {1, 1}},
FrameStyle->Directive[
RGBColor[0.4196078431372549, 0.6313725490196078, 0.4196078431372549], AbsoluteThickness[1],
Opacity[1]],
ImageSize->Automatic,
RoundingRadius->4,
StripOnInput->False], {1.7693034738587656, 0.851554354668779}],
"DynamicName",
BoxID -> "VertexID$8"],
TagBox[InsetBox[
FrameBox["8",
Background->Directive[
RGBColor[0.9607843137254902, 0.9882352941176471, 0.9764705882352941]],
BaseStyle->GrayLevel[0],
FrameMargins->{{2, 2}, {1, 1}},
FrameStyle->Directive[
RGBColor[0.4196078431372549, 0.6313725490196078, 0.4196078431372549], AbsoluteThickness[1],
Opacity[1]],
ImageSize->Automatic,
RoundingRadius->0,
StripOnInput->False], {1.3269776053940743, 0.}],
"DynamicName",
BoxID -> "VertexID$9"],
TagBox[InsetBox[
FrameBox["9",
Background->Directive[
RGBColor[0.9607843137254902, 0.9882352941176471, 0.9764705882352941]],
BaseStyle->GrayLevel[0],
FrameMargins->{{2, 2}, {1, 1}},
FrameStyle->Directive[
RGBColor[0.4196078431372549, 0.6313725490196078, 0.4196078431372549], AbsoluteThickness[1],
Opacity[1]],
ImageSize->Automatic,
RoundingRadius->0,
StripOnInput->False], {2.211629342323457, 0.}],
"DynamicName",
BoxID -> "VertexID$10"]}}]]],
AlignmentPoint->Center,
Axes->False,
AxesLabel->None,
AxesOrigin->Automatic,
AxesStyle->{},
Background->None,
BaseStyle->{},
BaselinePosition->Automatic,
ContentSelectable->Automatic,
DefaultBaseStyle->"TreeGraphics",
DisplayFunction->Identity,
Epilog->{},
FormatType->StandardForm,
Frame->False,
FrameLabel->None,
FrameStyle->{},
FrameTicks->None,
FrameTicksStyle->{},
GridLines->None,
GridLinesStyle->{},
ImageMargins->0.,
ImagePadding->All,
ImageSize->{151.62868202518266`, Automatic},
LabelStyle->{},
PlotLabel->None,
PlotRange->All,
PlotRangeClipping->False,
PlotRangePadding->Automatic,
PlotRegion->Automatic,
Prolog->{},
RotateLabel->True,
Ticks->Automatic,
TicksStyle->{}]\)]](https://www.wolframcloud.com/obj/resourcesystem/images/d41/d418c154-0208-4834-bfa2-4ad22869cd9f/7041e6fbb4cf7e1a.png) |
| Out[2]= |  |
Scope (1)
CaterpillarTreeQ also supports graphs:
| In[3]:= | ![ResourceFunction["CaterpillarTreeQ"][\!\(\*
GraphicsBox[
NamespaceBox["NetworkGraphics",
DynamicModuleBox[{Typeset`graph = HoldComplete[
Graph[{1, 2, 4, 3, 5, 6, 7, 8, 9}, {{{1, 2}, {2, 3}, {2, 4}, {2, 5}, {5, 6}, {6, 7}, {7, 8}, {7, 9}}, Null}]]},
TagBox[GraphicsGroupBox[
GraphicsComplexBox[{{0., 0.7999999999999998}, {0.8, 1.5999999999999999`}, {0.8, 0.7999999999999998}, {1.6, 0.7999999999999998}, {1.6, 2.4}, {2.4, 1.5999999999999999`}, {2.4, 0.7999999999999998}, {2., 0.}, {
2.8, 0.}}, {
{Hue[0.6, 0.7, 0.7], Opacity[0.7], CapForm["Round"], Arrowheads[
Medium], ArrowBox[{{1, 2}, {2, 3}, {2, 4}, {2, 5}, {5, 6}, {6, 7}, {
7, 8}, {7, 9}}, 0.02878787878787878]},
{Hue[0.6, 0.5, 1.], EdgeForm[{GrayLevel[0], Opacity[0.7]}], DiskBox[1, 0.02878787878787878], DiskBox[2, 0.02878787878787878], DiskBox[3, 0.02878787878787878], DiskBox[4, 0.02878787878787878], DiskBox[5, 0.02878787878787878], DiskBox[6, 0.02878787878787878], DiskBox[7, 0.02878787878787878], DiskBox[8, 0.02878787878787878], DiskBox[9, 0.02878787878787878]}}]],
MouseAppearanceTag["NetworkGraphics"]],
AllowKernelInitialization->False]],
DefaultBaseStyle->"NetworkGraphics",
FormatType->TraditionalForm,
FrameTicks->None]\)]](https://www.wolframcloud.com/obj/resourcesystem/images/d41/d418c154-0208-4834-bfa2-4ad22869cd9f/7422db5c3b06de65.png) |
| Out[3]= |  |
Properties and Relations (1)
Non-tree graphs are not caterpillar trees:
| In[4]:= | ![TreeGraphQ[\!\(\*
GraphicsBox[
NamespaceBox["NetworkGraphics",
DynamicModuleBox[{Typeset`graph = HoldComplete[
Graph[{1, 2, 3}, {{{1, 2}, {2, 3}, {3, 1}}, Null}]]},
TagBox[GraphicsGroupBox[
GraphicsComplexBox[{{-0.8660254037844384, -0.4999999999999994}, {0.8660254037844389, -0.5000000000000012}, {
1.8369701987210297`*^-16, 1.}}, {
{Hue[0.6, 0.7, 0.7], Opacity[0.7], CapForm["Round"], Arrowheads[
Medium], ArrowBox[{{1, 2}, {2, 3}, {3, 1}}, 0.020399597244776385`]},
{Hue[0.6, 0.5, 1.], EdgeForm[{GrayLevel[0], Opacity[0.7]}], DiskBox[1, 0.020399597244776385], DiskBox[2, 0.020399597244776385], DiskBox[3, 0.020399597244776385]}}]],
MouseAppearanceTag["NetworkGraphics"]],
AllowKernelInitialization->False]],
DefaultBaseStyle->"NetworkGraphics",
FormatType->TraditionalForm,
FrameTicks->None]\)]](https://www.wolframcloud.com/obj/resourcesystem/images/d41/d418c154-0208-4834-bfa2-4ad22869cd9f/2e6b67789df23c18.png) |
| Out[4]= |  |
Publisher
Requirements
Wolfram Language 14.0 (January 2024) or above
Version History
- 1.0.0 – 28 March 2025
Source Metadata
Related Resources
Related Symbols
License Information
This work is licensed under a Creative Commons Attribution 4.0 International License