Tree Number

Author

Eric W. Weisstein
July 2, 2026

This notebook downloaded from https://mathworld.wolfram.com/notebooks/GraphTheory/TreeNumber.nb.

For more information, see Eric's MathWorld entry https://mathworld.wolfram.com/TreeNumber.html.

©2026 Wolfram Research, Inc. except for portions noted otherwise

GraphDataCountTable

table=GraphDataCountTable["TreeNumber",{"Alkane"->000012,"Antiprism"->010701,"Barbell"->109613,"Book"->007395,"Centipede"->000012,"CocktailParty"->087156,"Complete"->008619,"CrossedPrism"->007395,"Cycle"->007395,"Dipyramid"->010701,"DoubleCone"->007395,"Empty"->000004,"Gear"->007395,{"Grid",2}->007395,"Helm"->007395,"Ladder"->040000,"LadderRung"->000027,"MoebiusLadder"->007395,"Pan"->007395,"Path"->057427,"PathComplement"->004526,"Prism"->007395,"Spoke n×n"->000012,"StackedPrism n×n"->007395,"Star"->057427,"Sunlet"->007395,"Trapezohedron"->007395,"TriangularHoneycombRook"->024206,"TriangularSnake"->007395,"Web"->007395,"Wheel"->007395}]

DateString[]

TextGrid[OEISUpdates[table],Dividers->All]

Parametrized families

<<MathWorld`Graphs`

Alkane

A000012

seq=Table[GraphData[{"Alkane",n},"TreeNumber"],{n,10}]

Codex 5.5 High

Every alkane graph is a tree.  Its edge set is already one tree, and no zero-tree decomposition is possible for a nonempty tree.  Hence TreeNumber(Alkane_n) = 1.

AlternatingGroupGraph

seq=Table[GraphData[{"AlternatingGroupGraph",n},"TreeNumber"],{n,2,6}]

Andrasfai

seq=Table[GraphData[{"Andrasfai",n},"TreeNumber"],{n,20}]

Antelope n×n

seq=Table[GraphData[{"Antelope",{n,n}},"TreeNumber"],{n,20}]

Antelope m×n

DeleteCases[
Flatten[Table[{
{m,n},
GraphData[{"Antelope",{m,n}},"TreeNumber"],
XXX
},{n,20},{m,n}],1],
{_,x_,x_}|{_,_GraphData,_}
]//Quiet

Antiprism

A010701

Entity["Graph",{"Antiprism",n}]["TreeNumber"]

seq=Table[GraphData[{"Antiprism",n},"TreeNumber"],{n,3,25}]

Codex 5.5 High

The n-antiprism graph has 2 n vertices and 4 n edges, so two trees can cover at most 2 (2 n - 1) edges; hence at least three trees are needed.  Label the two rim cycles a_1, ..., a_n and b_1, ..., b_n, with cycle edges a_i a_{i+1} and b_i b_{i+1}, spokes a_i b_i, and diagonals a_i b_{i-1}, using subscripts modulo n.  One tree is the path a_1 ... a_n together with all spokes a_i b_i.  A second tree is the path b_1 ... b_n together with the diagonals a_i b_{i-1} for i = 2, ..., n.  The third tree is the path b_1 b_n a_1 a_n.  These three edge-disjoint trees partition the edge set, so TreeNumber(Antiprism_n) = 3.

Apollonian

seq=Table[GraphData[{"Apollonian",n},"TreeNumber"],{n,6}]

Barbell

A109613

seq=Table[GraphData[{"Barbell",n},"TreeNumber"],{n,3,20}]

Codex 5.5 Extra High

The n-barbell graph consists of two copies of K_n joined by a single bridge.  Let q = Ceiling[n/2].  Any tree decomposition of K_n needs at least q trees, since K_n has Binomial[n, 2] edges and each tree on its n vertices has at most n - 1 edges.  In a tree decomposition of the barbell graph, only the tree containing the bridge can have edges from both complete subgraphs; every other tree is contained in one complete subgraph.  Removing the bridge from that one tree leaves at most one tree piece in each complete subgraph, so if t trees decompose the barbell graph, their nonempty intersections with the two complete subgraphs give at most t + 1 tree pieces.  Since each complete subgraph needs at least q pieces, t + 1 >= 2 q, and hence t >= 2 q - 1.  Conversely, take q-tree decompositions of the two copies of K_n as in the complete-graph construction, choosing in each copy a tree containing the bridge endpoint.  Joining those two chosen trees by the bridge gives one tree, and the remaining trees stay in their respective complete subgraphs.  Thus TreeNumber(Barbell_n) = 2 Ceiling[n/2] - 1.

Bishop n×n

seq=Table[GraphData[{"Bishop",{n,n}},"TreeNumber"],{n,20}]

Bishop m×n

Entity["Graph",{"Bishop",{m,n}}]["TreeNumber"]

DeleteCases[
Flatten[Table[{
{m,n},
GraphData[{"CompleteBipartite",{m,n}},"TreeNumber"],
XXX
},{n,20},{m,n}],1],
{_,x_,x_}|{_,_GraphData,_}]//Quiet

BlackBishop n×n

seq=Table[GraphData[{"BlackBishop",{n,n}},"TreeNumber"],{n,20}]

BlackBishop m×n

Entity["Graph",{"Bishop",{m,n}}]["TreeNumber"]

DeleteCases[
Flatten[Table[{
{m,n},
GraphData[{"BlackBishop",{m,n}},"TreeNumber"],
XXX
},{n,20},{m,n}],1],
{_,x_,x_}|{_,_GraphData,_}
]//Quiet

Book

A007395

seq=Table[GraphData[{"Book",n},"TreeNumber"],{n,20}]

Codex 5.5 High

The n-book graph contains a triangle, so one tree cannot contain all of its edges.  Let u v be the common spine edge and let w_i be the page vertices.  One tree consists of the spine edge u v together with all edges u w_i, and a second tree consists of all edges v w_i.  These two edge-disjoint trees partition the edge set, so TreeNumber(Book_n) = 2.

Bruhat

seq=Table[GraphData[{"Bruhat",n},"TreeNumber"],{n,6}]

Camel n×n

seq=Table[GraphData[{"Camel",{n,n}},"TreeNumber"],{n,20}]

Camel m×n

Entity["Graph",{"Camel",{m,n}}]["TreeNumber"]

DeleteCases[
Flatten[Table[{
{m,n},
GraphData[{"CompleteBipartite",{m,n}},"TreeNumber"],
XXX
},{n,20},{m,n}],1],
{_,x_,x_}|{_,_GraphData,_}]//Quiet

Cameron

seq=Table[GraphData[{"Cameron",n},"TreeNumber"],{n,20}]

Centipede

A000012

seq=Table[GraphData[{"Centipede",n},"TreeNumber"],{n,10}]

Codex 5.5 High

The n-centipede graph is a tree.  Its edge set is already one tree, and no zero-tree decomposition is possible for a nonempty tree.  Hence TreeNumber(Centipede_n) = 1.

CocktailParty

A087156

seq=Table[GraphData[{"CocktailParty",n},"TreeNumber"],{n,20}]

Codex 5.5 High

The 1-cocktail-party graph is edgeless, so its tree number is 0.  For n >= 2, the n-cocktail-party graph has 2 n vertices and 2 n (n - 1) edges, so at least Ceiling[2 n (n - 1)/(2 n - 1)] = n trees are needed.  For the matching upper bound, use Walecki's decomposition of K_(2 n) into n - 1 Hamiltonian cycles and one perfect matching, choosing the perfect matching to be the matching deleted from the cocktail-party graph.  In each Hamiltonian cycle choose one edge incident with a fixed vertex; these chosen edges are distinct and form a star.  Removing them turns the cycles into n - 1 Hamiltonian paths, and the chosen edges give one more tree.  Thus TreeNumber(CocktailParty_n) = Piecewise[{{0, n == 1}}, n].

Complete

A008619

Entity["Graph",{"Complete",n}]["TreeNumber"]

seq=Table[GraphData[{"Complete",n},"TreeNumber"],{n,30}]

Codex 5.5 High

For n >= 2, each tree in an edge-decomposition of K_n has at most n - 1 edges, so at least Ceiling[Binomial[n, 2]/(n - 1)] = Ceiling[n/2] trees are needed.  Walecki's decomposition of K_{2 m + 1} into m Hamiltonian cycles gives the matching upper bounds: deleting one fixed vertex from every cycle decomposes K_{2 m} into m Hamiltonian paths, while deleting one edge incident with a fixed vertex from each cycle decomposes K_{2 m + 1} into m Hamiltonian paths plus the star formed by the deleted edges.  The graph K_1 has no edges, so TreeNumber(K_n) = Piecewise[{{0, n == 1}}, Ceiling[n/2]].

CompleteBipartite n×n

Entity["Graph",{"CompleteBipartite",{n,n}}]["TreeNumber"]

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"TreeNumber"],{n,20}]

Table[Ceiling[n^2/(2 n-1)],{n,20}]

CompleteBipartite m×n

Entity["Graph",{"CompleteBipartite",{m,n}}]["TreeNumber"]

DeleteCases[
Flatten[Table[{
{m,n},
GraphData[{"CompleteBipartite",{m,n}},"TreeNumber"],
Ceiling[m n/(m+n-1)]
},{n,20},{m,n}],1],
{_,x_,x_}|{_,_GraphData,_}]//Quiet

CompleteTripartite n×n×n

Entity["Graph",{"CompleteTripartite",{n,n,n}}]["TreeNumber"]

seq=Table[GraphData[{"CompleteTripartite",{n,n,n}},"TreeNumber"],{n,10}]

Table[n+1,{n,10}]

CompleteTripartite k×m×n

Entity["Graph",{"CompleteTripartite",{k,m,n}}]["TreeNumber"]

DeleteCases[
Flatten[Table[{
{k,m,n},
GraphData[{"CompleteTripartite",{k,m,n}},"TreeNumber"],
Ceiling[(k m+k n+m n)/(k+m+n-1)]
},{n,10},{m,n},{k,m}],2],
{_,x_,x_}|{_,_GraphData,_}]//Quiet

CompleteTripartiteMinusPerfectMatching

seq=Table[GraphData[{"CompleteTripartiteMinusPerfectMatching",{2n,2n,2n}},"TreeNumber"],{n,10}]

CossidentePenttila

{
#,
q=GraphData[#,"NotationRules","CossidentePenttila"],
XXX,
GraphData[#,"TreeNumber"]
}&/@GraphData["CossidentePenttila"]

CrossedPrism

A007395

seq=Table[GraphData[{"CrossedPrism",2n},"TreeNumber"],{n,2,12}]

Codex 5.5 Extra High

The crossed-prism graph has a Hamiltonian cycle v_1 v_2 ... v_(2 n) v_1 and n crossed matching edges.  In the standard labeling, these matching edges are v_i v_(i+n-1) for odd i = 1, 3, ..., n - 1, v_i v_(i+n+1) for even i = 2, 4, ..., n - 2, and v_(n+1) v_(2 n).  One tree is the path v_1 v_2 ... v_(n+2).  The second tree contains the remaining cycle path v_(n+2) v_(n+3) ... v_(2 n) v_1 together with all crossed matching edges.  This second graph is a tree: its cycle edges form a path through v_(n+2), ..., v_(2 n), v_1, and every missing vertex v_2, ..., v_(n+1) is attached to that path by exactly one crossed matching edge.  These two trees partition all edges.  Since the crossed-prism graph contains a cycle, one tree is impossible, so TreeNumber(CrossedPrism_n) = 2.

Crown

seq=Table[GraphData[{"Crown",n},"TreeNumber"],{n,20}]

CubeConnectedCycle

Entity["Graph",{"CubeConnectedCycle",n}]["TreeNumber"]

seq=Table[GraphData[{"CubeConnectedCycle",n},"TreeNumber"],{n,3,8}]

ChatGPT 5.5 Pro Standard

For n = 3, the cube-connected cycle graph has 8 replacement 3-cycles and 12 cube edges, hence 24 vertices and 36 edges. Suppose its edges were partitioned into two trees R and B. Each replacement triangle must be split 2+1 between R and B, because neither tree can contain all three triangle edges. Let a be the number of triangles in which R receives two triangle edges, and let c be the number of cube edges in R. Then |E(R)| = 8 + a + c, so the vertex support of R has 9 + a + c vertices and R omits 15 - a - c vertices. A vertex omitted by R can occur only in a triangle where R has a single triangle edge, and each such triangle contributes at most one omitted vertex. Thus 15 - a - c <= 8 - a, so c >= 7. For B, |E(B)| = 36 - |E(R)| = 28 - a - c, so B omits 24 - (|E(B)| + 1) = a + c - 5 vertices. A vertex omitted by B can occur only in one of the a triangles where B has a single triangle edge, so a + c - 5 <= a, hence c <= 5. This contradiction shows that the truncated cubical graph, i.e. the 3-dimensional cube-connected cycle graph, cannot have tree number 2.

Cycle

A007395

Entity["Graph",{"Cycle",n}]["TreeNumber"]

seq=Table[GraphData[{"Cycle",n},"TreeNumber"],{n,3,30}]

Codex 5.5 High

A cycle is not a tree, so its tree number is at least 2.  Deleting any one cycle edge gives a path, and the deleted edge is also a tree.  These two edge-disjoint trees partition the edge set, so TreeNumber(C_n) = 2 for n >= 3.

CycleComplement

seq=Table[GraphData[{"CycleComplement",n},"TreeNumber"],{n,3,20}]

DiagonalIntersection

seq=Table[GraphData[{"DiagonalIntersection",n},"TreeNumber"],{n,3,14}]

Dipyramid

A010701

seq=Table[GraphData[{"Dipyramid",n},"TreeNumber"],{n,3,20}]

Codex 5.5 High

The n-dipyramid graph is obtained from an n-cycle by adding two nonadjacent apices adjacent to every cycle vertex.  It has n + 2 vertices and 3 n edges, so at least Ceiling[3 n/(n + 1)] = 3 trees are needed.  Label the cycle vertices v_1, ..., v_n and the apices a and b.  One tree is the path v_1 ... v_n together with a v_1.  A second tree consists of the edges a v_2, ..., a v_n and the cycle edge v_n v_1.  The third tree is the star with center b and leaves v_1, ..., v_n.  These three edge-disjoint trees partition the edge set, so TreeNumber(Dipyramid_n) = 3.

DorogovtsevGoltsevMendes

seq=Table[GraphData[{"DorogovtsevGoltsevMendes",n},"TreeNumber"],{n,0,7}]

DoubleCone

A007395

seq=Table[GraphData[{"DoubleCone",n},"TreeNumber"],{n,3,20}]

Codex 5.5 High

The n-double-cone graph has 2 n + 1 vertices and 4 n edges, so at least Ceiling[4 n/(2 n)] = 2 trees are needed.  For the upper bound, on each n-cycle choose a vertex x.  One tree contains the apex edge to x and the cycle with one edge incident to x deleted, for both cycles.  The second tree contains the remaining apex edges and the two deleted cycle edges.  Each subgraph is connected with 2 n edges on 2 n + 1 vertices, so both are trees and they partition the edge set.  Hence TreeNumber(DoubleCone_n) = 2.

Empty

A000004

Entity["Graph",{"Empty",n}]["TreeNumber"]

seq=Table[GraphData[{"Empty",n},"TreeNumber"],{n,30}]

Codex 5.5 High

The empty graph has no edges, so its edge set is decomposed into zero trees.  Hence TreeNumber(Empty_n) = 0.

ErectedPolygon

DeleteCases[Module[{n,r},
{
#,
{n,r}=GraphData[#,"NotationRules","ErectedPolygon"],
XXX,
GraphData[#,"TreeNumber"]
}
]&/@GraphData["ErectedPolygon"],
{__,x_,x_}]

FibonacciCube

seq=Table[GraphData[{"FibonacciCube",n},"TreeNumber"],{n,15}]

Fiveleaper n×n

seq=Table[GraphData[{"Fiveleaper",{n,n}},"TreeNumber"],{n,20}]

Fiveleaper m×n

Entity["Graph",{"Fiveleaper",{m,n}}]["TreeNumber"]

DeleteCases[
Flatten[Table[{
{m,n},
GraphData[{"Fiveleaper",{m,n}},"TreeNumber"],
XXX
},{n,20},{m,n}],1],
{_,x_,x_}|{_,_GraphData,_}]//Quiet

Flower

seq=Table[GraphData[{"Flower",n},"TreeNumber"],{n,5,20}]

FoldedCube

seq=Table[GraphData[{"FoldedCube",n},"TreeNumber"],{n,2,10}]

Gear

A007395

seq=Table[GraphData[{"Gear",n},"TreeNumber"],{n,3,20}]

Codex 5.5 High

The n-gear graph contains its rim cycle, so one tree cannot contain all edges.  Label the rim cycle so that the hub is adjacent to alternate rim vertices.  Deleting any one rim edge leaves a path, which is one tree.  The second tree consists of all hub spokes together with the deleted rim edge; this is a star with one extra leaf attached at a rim vertex.  These two edge-disjoint trees partition the edge set, so TreeNumber(Gear_n) = 2.

Giraffe n×n

seq=Table[GraphData[{"Giraffe",{n,n}},"TreeNumber"],{n,20}]

Giraffe m×n

Entity["Graph",{"Fiveleaper",{m,n}}]["TreeNumber"]

DeleteCases[
Flatten[Table[{
{m,n},
GraphData[{"Giraffe",{m,n}},"TreeNumber"],
XXX
},{n,20},{m,n}],1],
{_,x_,x_}|{_,_GraphData,_}]//Quiet

Goldberg

seq=Table[GraphData[{"Goldberg",n},"TreeNumber"],{n,3,20}]

Grid n×n

A007395

Entity["Graph",{"Grid",{n,n}}]["TreeNumber"]

seq=Table[GraphData[{"Grid",{n,n}},"TreeNumber"],{n,20}]

Codex 5.5 High

The 1 by 1 grid has no edges, so its tree number is 0.  For n >= 2, the n by n grid contains a 4-cycle, so one tree is not enough.  The rectangular-grid construction in the next subsection with m = n gives a decomposition into two trees: one tree is a first-row spine with vertical paths hanging from it, and the other is the remaining lower-row horizontal paths joined by one boundary column.  Hence TreeNumber(Grid_(n,n)) = Piecewise[{{0, n == 1}}, 2].

Grid m×n

Entity["Graph",{"Grid",{m,n}}]["TreeNumber"]

Sort@DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"Grid",{m,n}},"TreeNumber"],
Piecewise[{{0,m==n==1},{1,m==1||n==1}},2]
},{n,20},{m,n}],1],
{_,x_,x_}|{_,_GraphData,_}]//Quiet

Codex 5.5 High

For the m by n grid, the 1 by 1 case has tree number 0, and a one-row or one-column grid with more than one vertex is a path and has tree number 1.  Now suppose m, n >= 2, and label the vertices (i, j).  One tree contains all horizontal edges in row 1 and all vertical edges except those in column n between rows 2 through m.  This is a first-row spine with vertical paths attached.  The second tree contains all horizontal edges in rows 2 through m and the vertical edges in column n between rows 2 through m.  This is a column spine joining the lower-row paths.  These two edge-disjoint trees partition the grid edges, and the 4-cycle gives the lower bound 2, so TreeNumber(Grid_(m,n)) = Piecewise[{{0, m == 1 && n == 1}, {1, m == 1 || n == 1}}, 2].

Grid n×n×n

Entity["Graph",{"Grid",{n,n,n}}]["TreeNumber"]

seq=Table[GraphData[{"Grid",{n,n,n}},"TreeNumber"],{n,10}]

Grid k×m×n

Entity["Graph",{"Grid",{k,m,n}}]["TreeNumber"]

Sort@DeleteCases[Flatten[Table[{
{k,m,n},
GraphData[{"Grid",{k,m,n}},"TreeNumber"],
XXX
},{n,10},{m,n},{k,m}],2],
{_,x_,x_}|{_,_GraphData,_}]//Quiet

HalvedCube

seq=Table[GraphData[{"HalvedCube",n},"TreeNumber"],{n,10}]

Hanoi

seq=Table[GraphData[{"Hanoi",n},"TreeNumber"],{n,6}]

Helm

A007395

seq=Table[GraphData[{"Helm",n},"TreeNumber"],{n,3,20}]

Codex 5.5 High

The n-helm graph contains a rim cycle, so one tree cannot contain all of its edges.  Number the rim vertices cyclically.  One tree consists of all pendant edges, the rim path obtained by deleting the last rim edge, and the spoke at the first rim vertex.  The second tree consists of the deleted rim edge and all remaining spokes.  These two edge-disjoint trees partition the edge set, so TreeNumber(Helm_n) = 2.

Hypercube

Entity["Graph",{"Hypercube",n}]["TreeNumber"]

seq=Table[GraphData[{"Hypercube",n},"TreeNumber"],{n,0,10}]

Table[Piecewise[{{0,n==0}},Ceiling[(n+1)/2]],{n,0,10}]

KC

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"KC",{m,n}},"TreeNumber"],
XXX
},{n,3,10},{m,10}],1],{_,x_,x_}]

Keller

Entity["Graph",{"Keller",n}]["TreeNumber"]

seq=Table[GraphData[{"Keller",n},"TreeNumber"],{n,5}]

King n×n

seq=Table[GraphData[{"King",{n,n}},"TreeNumber"],{n,20}]

King m×n

Sort@DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"King",{m,n}},"TreeNumber"],
XXX
},{n,20},{m,n}],1],
{_,x_,x_}|{_,_GraphData,_}]//Quiet

Knight n×n

Entity["Graph",{"Knight",{n,n}}]["TreeNumber"]

seq=Table[GraphData[{"Knight",{n,n}},"TreeNumber"],{n,20}]

Knight m×n

Entity["Graph",{"Knight",{m,n}}]["TreeNumber"]

Sort@DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"King",{m,n}},"TreeNumber"],
XXX
},{n,20},{m,n}],1],
{_,x_,x_}|{_,_GraphData,_}]//Quiet

KP

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"KP",{m,n}},"TreeNumber"],
XXX
},{n,10},{m,10}],1],
{_,x_,x_}|{_,_GraphData,_}]//Quiet

Ladder

A040000

Entity["Graph",{"Ladder",n}]["TreeNumber"]

seq=Table[GraphData[{"Ladder",n},"TreeNumber"],{n,20}]

Codex 5.5 High

The 1-ladder graph is a single edge, so its tree number is 1.  For n >= 2, the ladder graph contains a 4-cycle, so one tree cannot contain all edges.  One tree consists of one length n - 1 side path together with all n rungs, and the second tree is the other side path.  These two edge-disjoint trees partition the edge set, so TreeNumber(Ladder_n) = Piecewise[{{1, n == 1}}, 2].

LadderRung

A000027

seq=Table[GraphData[{"LadderRung",n},"TreeNumber"],{n,20}]

Table[n,{n,20}]

Codex 5.5 High

The n-ladder-rung graph is a matching with n nontrivial connected components.  Tree number is additive over connected components, and each isolated edge is itself a tree.  Hence TreeNumber(LadderRung_n) = n.

LindgrenSousselier

seq=Table[GraphData[{"LindgrenSousselier",n},"TreeNumber"],{n,11}]

LucasCube

seq=Table[GraphData[{"LucasCube",n},"TreeNumber"],{n,15}]

MengerSponge

seq=Table[GraphData[{"MengerSponge",n},"TreeNumber"],{n,3}]

MoebiusLadder

A007395

Entity["Graph",{"MoebiusLadder",n}]["TreeNumber"]

seq=Table[GraphData[{"MoebiusLadder",n},"TreeNumber"],{n,3,25}]

Codex 5.5 High

The n-Moebius ladder contains a cycle, so one tree cannot contain all edges.  Write it as a ladder with top vertices t_0, ..., t_(n-1), bottom vertices b_0, ..., b_(n-1), rungs t_i b_i, side paths t_0 ... t_(n-1) and b_0 ... b_(n-1), and twist edges t_(n-1) b_0 and b_(n-1) t_0.  One tree is the bottom path b_0 ... b_(n-1), the twist edge b_(n-1) t_0, and the top edge t_0 t_1.  The second tree contains the other top-path edges, the other twist edge, and all rungs.  These two edge-disjoint trees partition the edge set, so TreeNumber(MoebiusLadder_n) = 2.

Mycielski

Entity["Graph",{"Mycielski",n}]["TreeNumber"]

seq=Table[GraphData[{"Mycielski",n},"TreeNumber"],{n,11}]

Necklace

seq=Table[GraphData[{"Necklace",n},"TreeNumber"],{n,10}]

Odd

Entity["Graph",{"Odd",n}]["TreeNumber"]

seq=Table[GraphData[{"Odd",n},"TreeNumber"],{n,7}]

Paley

{
#,
q=GraphData[#,"NotationRules","Paley"],
XXX,
GraphData[#,"TreeNumber"]
}&/@GraphData["Paley"]

Pan

A007395

seq=Table[GraphData[{"Pan",n},"TreeNumber"],{n,3,20}]

Codex 5.5 High

The n-pan graph is an n-cycle with one pendant edge attached.  The cycle prevents a one-tree decomposition.  Deleting one cycle edge leaves a tree containing the pendant edge, and the deleted edge is itself a tree.  These two edge-disjoint trees partition the edge set, so TreeNumber(Pan_n) = 2.

Path

A057427

Entity["Graph",{"Path",n}]["TreeNumber"]

seq=Table[GraphData[{"Path",n},"TreeNumber"],{n,20}]

Table[Piecewise[{{0,n==1}},1],{n,20}]

Codex 5.5 High

The one-vertex path has no edges, so its tree number is 0.  Every path with at least one edge is already a tree, so one tree is necessary and sufficient.  Therefore TreeNumber(P_n) = Piecewise[{{0, n == 1}}, 1].

PathComplement

A004526

seq=Table[GraphData[{"PathComplement",n},"TreeNumber"],{n,20}]

Codex 5.5 High

The complement of P_n has Binomial[n, 2] - (n - 1) = (n - 1) (n - 2)/2 edges, so any tree decomposition needs at least Ceiling[((n - 1) (n - 2)/2)/(n - 1)] = Floor[(n - 1)/2] trees.  For even n = 2 r, take a Walecki decomposition of K_(2 r) into r Hamiltonian paths, with one path chosen to be P_n; the remaining r - 1 Hamiltonian paths decompose the complement.  For odd n = 2 r + 1, take a Walecki decomposition of K_(2 r + 1) into r Hamiltonian cycles, with one cycle chosen to be P_n plus the closing edge.  The other r - 1 cycles, with one edge incident to a fixed vertex deleted from each, give r - 1 Hamiltonian paths; the deleted edges together with the closing edge form a star.  Thus TreeNumber(complement(P_n)) = Floor[(n - 1)/2].

Peisert

{
#,
q=GraphData[#,"NotationRules","Peisert"],
XXX,
GraphData[#,"TreeNumber"]
}&/@GraphData["Peisert"]

Pell

seq=Table[GraphData[{"Pell",n},"TreeNumber"],{n,9}]

PlummerToft

seq=Table[GraphData[{"PlummerToft",n},"TreeNumber"],{n,20}]

Codex 5.5 High

For the Plummer-Toft family, n = 1 is the triangular prism and has tree number 2.  The n = 2 graph has two edge-disjoint trees with edge sets {12, 13, 14, 25, 27, 46} and {17, 23, 36, 37, 45, 56}.  The n = 3 graph has three edge-disjoint trees with edge sets {12, 13, 14, 15, 16, 27, 38}, {28, 34, 35, 36, 67, 78}, and {45, 56}.  For n >= 4, the standard labeling has the path v_1 ... v_(n+5), extra edges v_1 v_4, v_1 v_i for 5 <= i <= n + 4, v_4 v_i for 6 <= i <= n + 4, and v_2 v_(n+5), v_3 v_(n+5).  One tree is the path v_1 ... v_(n+4) together with v_2 v_(n+5).  A second tree is the star centered at v_1 with leaves v_4, v_5, ..., v_(n+4).  A third tree consists of the edges v_4 v_i for 6 <= i <= n + 4 together with v_(n+4) v_(n+5) and v_3 v_(n+5).  These trees partition the edge set.  The edge count is 3 n + 6 on n + 5 vertices, giving the lower bound 2 for n <= 2 and 3 for n >= 3, so TreeNumber(PlummerToft_n) = Piecewise[{{2, n <= 2}}, 3].

Prism

A007395

Entity["Graph",{"Prism",n}]["TreeNumber"]

seq=Table[GraphData[{"Prism",n},"TreeNumber"],{n,3,25}]

Codex 5.5 High

The n-prism graph contains a cycle, so one tree cannot contain all edges.  Label the two rim cycles t_1, ..., t_n and b_1, ..., b_n, with rungs t_i b_i.  One tree consists of the bottom path b_1 ... b_n, the top edge t_1 t_n, and the rung t_1 b_1.  The second tree consists of the top path t_1 ... t_n, the rungs t_i b_i for i = 2, ..., n, and the bottom edge b_n b_1.  These two edge-disjoint trees partition the edge set, so TreeNumber(Prism_n) = 2.

Queen n×n

seq=Table[GraphData[{"Queen",{n,n}},"TreeNumber"],{n,20}]

Queen m×n

Sort@DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"Queen",{m,n}},"TreeNumber"],
XXX
},{n,20},{m,n}],1],
{_,x_,x_}|{_,_GraphData,_}]//Quiet

Rook n×n

seq=Table[GraphData[{"Rook",{n,n}},"TreeNumber"],{n,20}]

Rook m×n

Sort@DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"Rook",{m,n}},"TreeNumber"],
XXX
},{n,20},{m,n}],1],
{_,x_,x_}|{_,_GraphData,_}]//Quiet

RookComplement n×n

seq=Table[GraphData[{"RookComplement",{n,n}},"TreeNumber"],{n,20}]

RookComplement m×n

Sort@DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"RookComplement",{m,n}},"TreeNumber"],
XXX
},{n,20},{m,n}],1],
{_,x_,x_}|{_,_GraphData,_}]//Quiet

SierpinskiCarpet

seq=Table[GraphData[{"SierpinskiCarpet",n},"TreeNumber"],{n,4}]

SierpinskiGasket

seq=Table[GraphData[{"SierpinskiGasket",n},"TreeNumber"],{n,7}]

SierpinskiTetrahedron

seq=Table[GraphData[{"SierpinskiTetrahedron",n},"TreeNumber"],{n,6}]

Spoke n×n

A000012

seq=Table[GraphData[{"Spoke",{n,n}},"TreeNumber"],{n,5}]

Codex 5.5 High

The m by n spoke graph consists of m internally disjoint paths of length n sharing a single endpoint.  It is connected and has m n + 1 vertices and m n edges, so it is a tree.  Its edge set is already one tree, and no zero-tree decomposition is possible for a nonempty tree.  In particular, TreeNumber(Spoke_(n,n)) = 1.

StackedBook n×n

seq=Table[GraphData[{"StackedBook",{n,n}},"TreeNumber"],{n,10}]

StackedBook m×n

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"StackedBook",{m,n}},"TreeNumber"],
XXX
},{n,10},{m,n}],1],{_,x_,x_}]

StackedPrism n×n

A007395

seq=Table[GraphData[{"StackedPrism",{n,n}},"TreeNumber"],{n,3,5}]

Codex 5.5 High

The n by n stacked-prism graph is the special case m = n of the m by n stacked-prism graph.  The construction in the next subsection partitions its edge set into two trees, and the graph contains a cycle, so one tree is not enough.  Hence TreeNumber(StackedPrism_(n,n)) = 2 for every valid n.

StackedPrism m×n

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"StackedPrism",{m,n}},"TreeNumber"],
2
},{m,3,8},{n,5}],1],
{_,x_,x_}]

Codex 5.5 High

The m by n stacked-prism graph is the Cartesian product C_m square P_n.  Label its vertices v_(i,j), with i modulo m and j = 1, ..., n.  Let T_1 contain the path edges v_(i,j) v_(i+1,j) for i = 1, ..., m - 1 and j = 1, ..., n - 1, the single top edge v_(1,n) v_(2,n), and the vertical edges v_(1,j) v_(1,j+1).  This is a tree: it is a first-column spine with row paths attached, plus one final leaf edge.  Let T_2 contain all remaining edges.  The vertices with i = 2, ..., m, all vertical edges in those columns, and the top-row path v_(2,n) ... v_(m,n) form a tree; each vertex v_(1,j) is attached to it by the remaining cycle edge v_(m,j) v_(1,j).  Thus T_2 is connected and has m n - 1 edges, so it is also a tree.  Since T_1 and T_2 partition all edges and a cycle gives the lower bound two, TreeNumber(StackedPrism_(m,n)) = 2.

Star

A057427

Entity["Graph",{"Star",n}]["TreeNumber"]

seq=Table[GraphData[{"Star",n},"TreeNumber"],{n,25}]

Codex 5.5 High

The one-vertex star has no edges, so its tree number is 0.  Every nontrivial star is itself a tree, so exactly one tree decomposes its edge set.  Hence TreeNumber(Star_n) = Piecewise[{{0, n == 1}}, 1].

Sun

seq=Table[GraphData[{"Sun",n},"TreeNumber"],{n,3,20}]

Sunlet

A007395

seq=Table[GraphData[{"Sunlet",n},"TreeNumber"],{n,3,20}]

Codex 5.5 High

The n-sunlet graph is an n-cycle with one pendant edge attached to each cycle vertex.  The cycle gives the lower bound 2.  Removing one cycle edge leaves a tree containing all pendant edges, and the removed edge is itself a tree.  These two edge-disjoint trees partition the edge set, so TreeNumber(Sunlet_n) = 2.

Tetrahedral

seq=Table[GraphData[{"Tetrahedral",n},"TreeNumber"],{n,6,10}]

TorusGrid n×n

seq=Table[GraphData[{"TorusGrid",{n,n}},"TreeNumber"],{n,3,20}]

TorusGrid m×n

Sort@DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"TorusGrid",{m,n}},"TreeNumber"],
XXX
},{n,3,20},{m,3,n}],1],
{_,x_,x_}|{_,_GraphData,_}]//Quiet

Transposition

Entity["Graph",{"Transposition",n}]["TreeNumber"]

seq=Table[GraphData[{"Transposition",n},"TreeNumber"],{n,6}]

Trapezohedron

A007395

Entity["Graph",{"Trapezohedron",n}]["TreeNumber"]

seq=Table[GraphData[{"Trapezohedron",n},"TreeNumber"],{n,3,20}]

Codex 5.5 High

The n-trapezohedron graph has a 2 n-cycle and two apices, one adjacent to the odd cycle vertices and the other adjacent to the even cycle vertices.  The cycle gives the lower bound 2.  Put all but one cycle edge into the first tree; this is a path.  Put the omitted cycle edge and all apex edges into the second tree.  The apex edges form two disjoint stars, and the omitted cycle edge joins them into one tree.  These two edge-disjoint trees partition the edge set, so TreeNumber(Trapezohedron_n) = 2.

Triangular

seq=Table[GraphData[{"Triangular",n},"TreeNumber"],{n,2,20}]

TriangularGrid

seq=Table[GraphData[{"TriangularGrid",n},"TreeNumber"],{n,0,20}]

TriangularHoneycombAcuteKnight

seq=Table[GraphData[{"TriangularHoneycombAcuteKnight",n},"TreeNumber"],{n,20}]

TriangularHoneycombBishop

seq=Table[GraphData[{"TriangularHoneycombBishop",n},"TreeNumber"],{n,20}]

TriangularHoneycombObtuseKnight

seq=Table[GraphData[{"TriangularHoneycombObtuseKnight",n},"TreeNumber"],{n,20}]

TriangularHoneycombQueen

seq=Table[GraphData[{"TriangularHoneycombQueen",n},"TreeNumber"],{n,20}]

TriangularHoneycombRook

A024206

seq=Table[GraphData[{"TriangularHoneycombRook",n},"TreeNumber"],{n,20}]

Table[Floor[(n+1)^2/4]-1,{n,20}]

Codex 5.5 High

The n-triangular-honeycomb-rook graph is the disjoint union of complete graphs K_1, K_2, ..., K_n.  Tree number is additive over connected components, K_1 contributes 0, and TreeNumber(K_k) = Ceiling[k/2] for k >= 2.  Therefore TreeNumber(TriangularHoneycombRook_n) = Sum[Ceiling[k/2], {k, 2, n}] = Floor[(n + 1)^2/4] - 1.

TriangularSnake

A007395

seq=Table[GraphData[{"TriangularSnake",n},"TreeNumber"],{n,1,20,2}]

Codex 5.5 High

The one-vertex triangular snake has no edges, so its tree number is 0.  For n = 2 r + 1 >= 3, view the triangular snake as r triangles T_i with vertices u_(i-1), w_i, u_i, where consecutive triangles meet only in the cut vertex u_i.  One tree contains the edges u_(i-1) w_i and w_i u_i for all i, forming the path u_0 w_1 u_1 w_2 ... w_r u_r.  The second tree contains the remaining edges u_(i-1) u_i for all i, forming the path u_0 u_1 ... u_r.  These two edge-disjoint trees partition the edge set, and the presence of a triangle shows that one tree is impossible.  Hence TreeNumber(TriangularSnake_n) = Piecewise[{{0, n == 1}}, 2] for valid odd n.

TruncatedSquareLattice n×n

seq=Table[GraphData[{"TruncatedSquareLattice",{n,n}},"TreeNumber"],{n,10}]

TruncatedSquareLattice m×n

Sort@DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"TruncatedSquareLattice",{m,n}},"TreeNumber"],
XXX
},{n,20},{m,n}],1],
{_,x_,x_}|{_,_GraphData,_}]//Quiet

Web

A007395

seq=Table[GraphData[{"Web",n},"TreeNumber"],{n,3,20}]

Codex 5.5 High

The n-web graph is an n-prism with one pendant edge attached to each vertex of one rim cycle.  The prism subgraph contains a cycle, so one tree is not enough.  Use the two-tree prism decomposition, and add all pendant edges to the tree containing their rim endpoints.  Adding pendant edges to a tree preserves acyclicity and connectivity, so the two trees partition the web graph's edge set.  Hence TreeNumber(Web_n) = 2.

Wheel

A007395

Entity["Graph",{"Wheel",n}]["TreeNumber"]

seq=Table[GraphData[{"Wheel",n},"TreeNumber"],{n,4,20}]

Codex 5.5 High

The wheel graph W_n contains a rim cycle, so one tree cannot contain all edges.  Number the rim vertices cyclically.  One tree consists of the rim path obtained by deleting the last rim edge together with the spoke at the first rim vertex.  The second tree consists of the deleted rim edge and all remaining spokes.  These two edge-disjoint trees partition the edge set, so TreeNumber(W_n) = 2.

WheelComplement

seq=Table[GraphData[{"WheelComplement",n},"TreeNumber"],{n,4,20}]

WhiteBishop n×n

seq=Table[GraphData[{"WhiteBishop",{n,n}},"TreeNumber"],{n,2,20}]

WhiteBishop m×n

Sort@DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"WhiteBishop",{m,n}},"TreeNumber"],
XXX
},{n,20},{m,n}],1],
{_,x_,x_}|{_,_GraphData,_}]//Quiet

WhiteCamel n×n

seq=Table[GraphData[{"Bishop",{n,n}},"TreeNumber"],{n,{5}}]

Zebra n×n

seq=Table[GraphData[{"Zebra",{n,n}},"TreeNumber"],{n,20}]

Zebra m×n

Sort@DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"Zebra",{m,n}},"TreeNumber"],
XXX
},{n,20},{m,n}],1],
{_,x_,x_}|{_,_GraphData,_}]//Quiet