# A Structural Property of Trees with an Application to Vertex-Arboricity

Authors: Ming-jia Wang; Jing-ti Han
Journal: Mathematical Problems in Engineering
 (2017)

---

## Abstract

We provide a structural property of trees, which is applied to show that if a plane graphG contains two edge-disjoint spanning trees, then its dual graph G⁎ has the vertex-arboricity at most 2. We also show that every maximal plane graph of order at least 4 contains two edge-disjoint spanning trees.


---

## Body

## 1. Introduction

All graphs considered in this paper are finite simple graphs. Given graphG, let V(G), E(G), |G|, and G denote its vertex set, edge set, vertex number, and edge number, respectively. For a vertex v∈V(G), let dG(v) denote the degree of v in G. Moreover, let Δ(G) and δ(G) denote the maximum degree and minimum degree of G, respectively. Atree is a connected graph without cycles. Aplane graph is a particular drawing of a planar graph on the Euclidean plane.A subgraphH of G is called aspanning one if V(H)=V(G). A plane graph G is calledmaximal if every face of G is a triangle. A connectedEulerian graph is a connected one that contains no vertices of degree odd. Thedual, denoted by G∗, of a plane graph G is a plane graph whose vertices correspond to the faces of G and edges correspond to the edges of G in this way: if e is an edge of G incident to faces f1,f2, then the endpoints of the dual edge e∗∈E(G∗) are vertices v1,v2 of G∗ that represent the faces of f1,f2 of G. Thevertex-arboricitya(G) of a graph G is the minimum number of subsets into which V(G) can be partitioned so that each subset induces a forest.The vertex-arboricity of a graph was first introduced by Chartrand et al. [1], named aspoint-arboricity. Among other things, they proved that the vertex-arboricity of planar graphs is at most 3. Chartrand and Kronk [2] showed that this bound is sharp by presenting a planar graph of the vertex-arboricity 3. More generally, Kronk [3] showed that if S is a surface with Euler genus g, then a(S)=3 and if S is the sphere or the Klein bottle, then a(S)=⌊(9+1+24g)/4⌋. Hara et al. [4] extended partially Kronk’s result by proving that la(S)=3 if S is the projective plane or the torus, and la(S)≤4 if S is the Klein bottle. Here the vertex-arboricity of surface S is defined to be the maximum of the vertex-arboricity of all graphs embeddable into S. Other results about the vertex-arboricity of embedded graphs in the surface are referred to in [5–8].The following theorem, due to Stein [9], characterizes completely maximal plane graphs with vertex-arboricity 2.Theorem 1.
LetG be a maximal plane graph with |G|≥4. Then a(G)=2 if and only if G∗ is Hamiltonian.Hakimi and Schmeichel [10] extended Stein’s theorem to the following form.Theorem 2.
LetG be a plane graph. Then a(G)=2 if and only if G∗ contains a connected Eulerian spanning subgraph.Note that determining whether a graph to have a connected Eulerian spanning subgraph is quite difficult. Thus a natural question is as follows: which plane graphs have a connected Eulerian spanning subgraph? In this paper, we provide a sufficient condition about the problem.


## 2. Structural Property

LetP=(x,y) denote a path from vertex x to vertex y. We call a vertex of degree 1 aleaf in a tree. The following lemma is of interest by itself.Theorem 3.
LetT be a tree with T≥2 and n≥1 be an integer. If S⊆V(T) with S=2n≤T, then S can be partitioned into two sets X=x1,x2,…,xn and Y={y1,y2,…,yn} such that T contains n edge-disjoint paths Pi=xi,yi,i=1,2,…,n.Proof.
The proof is proceeded by induction on the order ofT. If 2≤|T|≤3, then T is a path of length 1 or 2. Note that n=1 in this case, so the theorem holds trivially. Suppose that T is a tree with |T|≥4. Let S be a subset of V(T) with S=2n≤T. If T contains a leaf v which is not in S, then S≤T-1. Let T′=T-v. Then T′ is a tree of order T-1 and S⊆VT′ satisfies S=2n≤T-1=T′. By the induction hypothesis, S can be partitioned into two sets X={x1,x2,…,xn} and Y={y1,y2,…,yn} such that T′ contains n edge-disjoint paths Pi=xi,yi,i=1,2,…,n. Clearly, S=X∪Y also is a required partition of T.
So assume thatS contains all the leaves of T. If there exist two leaves x and y adjacent to a common vertex u, we let T′=T-{x,y} and S′=S∖{x,y}. Then T′ is a tree of order |T|-2 and S′⊆V(T′) satisfies |S′|=|S|-2=2n-2≤|T|-2=|T′|. By the induction hypothesis, S′ can be partitioned into two sets X′={x1,x2,…,xn-1} and Y′={y1,y2,…,yn-1} such that T′ contains n-1 edge-disjoint paths Pi′=(xi,yi), i=1,2,…,n-1. Defining Pn=xuy, Pi=Pi′ for i=1,2,…,n-1, X=X′∪{x}, and Y=Y′∪{y}, we obtain a desired partition S=X∪Y of T.
Now suppose that every vertex ofT is adjacent to at most one leaf. Let Q=v1v2v3⋯vk be a longest path in T. Then it is easy to see that k≥4 and v1,vk are leaves. If v2 is adjacent to some vertex, u1, different from v1 and v3, then u1 is not a leaf by the assumption. There exists a vertex u2, other than v2, adjacent to u1. However, Q′=u2u1v2v3⋯vk is a path whose length is greater than that of Q, contradicting the choice of Q. Hence it follows that dT(v2)=2. Similarly, we derive that dT(vk-1)=2.
Ifv2∈S, we define T′=T-{v1,v2} and S′=S∖{v1,v2}. Then S′⊆V(T′) satisfies |S′|=|S|-2=2n-2≤|T|-2=|T′|. By the induction hypothesis, S′ admits a required partition X′∪Y′ with |X′|=|Y′|=n-1 so that T′ contains n-1 edge-disjoint paths P1,P2,…,Pn-1. In T, we define Pn=v1v2, X=X′∪{v1}, and Y=Y′∪{v2}.
Ifv2∉S, then |S|≤|T|-1. Let T′=T-v2+v1v3 and S′=S. Then T′ is a tree of order |T|-1 and S′⊆V(T′) with |S′|=2n≤|T|-1=|T′|. By the induction hypothesis, S′ can be partitioned into two sets X′={x1,x2,…,xn} and Y′={y1,y2,…,yn} such that T′ contains n edge-disjoint paths Pi′=xi,yi,i=1,2,…,n. Since v1 is a leaf of T′, v1 is an end of some path Pi0′. Furthermore, v1v3∈E(Pi0′). Without loss of generality, suppose that i0=n and Pn=v1v3z1z2⋯zm. In T, we let X=X′, Y=Y′, Pn=v1v2v3z1z2⋯zm, and Pi=Pi′ for i=1,2,…,n-1. A desired partition of S in T is established. This proves the theorem.By means of Theorem3, we can give a simple proof for the following result.Theorem 4.
LetG be a graph with G≥4. If G contains two edge-disjoint spanning trees, then G contains a connected Eulerian spanning subgraph.Proof.
Suppose thatT1 and T2 are two edge-disjoint spanning trees of G. Then V(T1)=V(T2)=V(G). Let S∗ denote the subset of vertices of degree odd in T1. Then S∗ is even. Since T1 contains at least two leaves, 2≤S∗=2n≤T1=T2. Since S∗⊆VT2, by Theorem 3, S∗ can be partitioned into two sets X={x1,x2,…,xn} and Y={y1,y2,…,yn} such that T2 contains n edge-disjoint paths Pi=(xi,yi), i=1,2,…,n.
LetM denote the subgraph of G induced by the edge set E(P1)∪⋯∪E(Pn). Let H=T1∪M. T1 is connected and spanning, so is H. Let v∈V(H)=V(G). It is easy to observe that dH(v)=dT1(v)+dM(v). If v∉S∗, then both dT1(v) and dM(v) are even, and hence dH(v) is even. If v∈S∗, then both dT1(v) and dM(v) are odd, and so dH(v) is even. It follows that H is Eulerian. Thus H is a connected Eulerian spanning subgraph of G. The proof of the theorem is complete.Combining Theorems2 and 4, we obtain the main result in this paper.Theorem 5.
LetG be a plane graph. If G∗ contains two edge-disjoint spanning trees, then a(G)=2.


## 3. Spanning Trees in Maximal Plane Graphs

LetG be a maximal plane graph. Then the following properties (a)–(d) hold:(a)
G=3G-6;(b)
3≤δG≤5 if G≥4;(c)
Each of the faces inG is of degree 3;(d)
IfG=3, then G is isomorphic to K3; if |G|=4, then G is isomorphic to K4; if G=5, then G is isomorphic to K5-e, where e is any edge of K5. In particular, when G≥5, we have that ΔG≥4.Theorem 6.
Every maximal plane graphG with ΔG≥3 contains two edge-disjoint spanning trees.Proof.
We prove the theorem by induction on the vertex number|G|. Since Δ(G)≥3, it follows that G≥4. If G=4, then G is isomorphic to K4, and K4 can be easily edge-partitioned into two edge-disjoint spanning trees. Hence the basis step of induction is established. Let G be a maximal plane graph with G≥5. So Δ(G)≥4. By the above property (b), G contains a vertex v with 3≤dGv≤5. Set k=dGv. Let v0,v1,…,vk-1 denote the neighbors of v in G in clockwise order and f0,f1,…,fk-1 denote the incident faces of v in G in clockwise order with vvi,vvi+1 as two boundary edges of fi for i=0,1,…,k-1. Here all the indices are taken modulo k. Note that f0,f1,…,fk-1 are all 3 faces.
The proof is split into the following three cases, depending on the size ofk.
Case
1
(
k
=
3
). Let G′=G-v. Then G′ is a maximal plane graph with |G′|<|G| and Δ(G′)≥Δ(G)-1≥3. By the induction hypothesis, G′ contains two edge-disjoint spanning trees T1′ and T2′. Let T1=T1′+vv1 and T2=T2′+vv2. Obviously, Ti is a spanning tree of G for i=1,2, and E(T1)∩E(T2)=∅. Thus, the theorem holds in this situation.
Case
2
(
k
=
4
). In view of the planarity of G, at least one of v0v2 and v1v3 does not belong to E(G). Without loss of generality, assume that v0v2∉E(G). Let G′=G-v+v0v2. Then G′ is a maximal plane graph with |G′|<|G| and Δ(G′)≥Δ(G)-1≥3. By the induction hypothesis, G′ contains two edge-disjoint spanning trees T1′ and T2′. If v0v2∉E(T1′)∪E(T2′), then we define Ti=Ti′+vvi for i=1,2. If v0v2∈E(T1′), then we define T1=(T1′-v0v2)+{vv0,vv2} and T2=T2′+vv1. If v0v2∈E(T2′), then we define T1=T1′+vv1 and T2=(T2′-v0v2)+{vv0,vv2}. It is easy to inspect that T1 and T2 are two edge-disjoint spanning trees of G in each of the above three cases.
Case
3
(
k
=
5
). Again, by the planarity of G, there exists a vertex vi, say i=0, such that v0v2,v0v3∉E(G). Let G′=G-v+{v0v2,v0v3}. Then G′ is a maximal plane graph with |G′|<|G| and Δ(G′)≥Δ(G)-1≥3. By the induction hypothesis, G′ contains two edge-disjoint spanning trees T1′ and T2′. We have to consider the following subcases.
Case
3.1. At least one of v0v2 and v0v3 does not belong to E(T1′)∪E(T2′), say v0v3∉E(T1′)∪E(T2′).
Ifv0v2∉E(T1′)∪E(T2′), then we set Ti=Ti′+vvi for i=1,2. If v0v2∈E(T1′), then we set T1=(T1′-v0v2)+{vv0,vv2} and T2=T2′+vv3. If v0v2∈E(T2′), then we set T1=T1′+vv1 and T2=(T2′-v0v2)+{vv0,vv2}.
Case
3.2
v
0
v
2
,
v
0
v
3
∈
E
T
1
′
∪
E
T
2
′. We need to deal with the following two subcases by symmetry.
Case
3.2.1
(
v
0
v
2
,
v
0
v
3
∈
E
(
T
i
′
)
for some
i
∈
1,2
). Without loss of generality, assume that i=1. It is enough to set T1=(T1′-{v0v2,v0v3})+{vv0,vv2,vv3} and T2=T2′+vv1.
Case
3.2.2
(
v
0
v
2
∈
E
(
T
1
′
)
and
v
0
v
3
∈
E
(
T
2
′
)
). Let A1 and B1 denote the two components of T1′-v0v2 with v0∈V(A1) and v2∈V(B1), and A2 and B2 denote the two components of T2′-v0v3 with v0∈V(A2) and v3∈V(B2). Since v0v2 is a cut edge of T1′, it follows that v1 belongs to exactly one of V(A1) and V(B1). Similarly, v4 belongs to exactly one of V(A2) and V(B2).
Ifv1∈V(A1), then we define T1=(T1′-v0v2)+{vv1,vv2} and T2=(T2′-v0v3)+{vv0,vv3}.
Ifv4∈V(A2), then we define T1=(T1′-v0v2)+{vv0,vv2} and T2=(T2′-v0v3)+{vv3,vv4}.
Now assume thatv1∈V(B1) and v4∈V(B2). This implies that v0v1∉E(T1′) and v0v4∉E(T2′). If v0v1∉E(T2′), then we define T1=(T1′-v0v2)+{v0v1,vv1} and T2=(T2′-v0v3)+{vv0,vv3}. If v0v4∉E(T1′), then we define T1=(T1′-v0v2)+{vv0,vv2} and T2=(T2′-v0v3)+{v0v4,vv4}. Otherwise, v0v1∈E(T2′) and v0v4∈E(T1′). It suffices to define T1=T1′-v0v2+vv2,vv4 and T2=T2′-v0v3+vv1,vv3.
It is easy to inspect thatT1 and T2 are two edge-disjoint spanning trees of G in every possible case above. This completes the proof of the theorem.The following consequence follows immediately from Theorems4 and 6.Corollary 7.
Every maximal planar graphG with G≥4 contains a connected Eulerian spanning subgraph.



---

*Source: 4259810-2017-06-11.xml*