Graph with boundary

Graph with boundary --- граф с границей.

A graph with boundary is a graph [math]\displaystyle{ G(V_{0} \cup \partial V, E_{0} \cup \partial E) }[/math] with interior vertices [math]\displaystyle{ V_{0} }[/math], boundary vertices [math]\displaystyle{ \partial V }[/math] and edge set [math]\displaystyle{ E_{0} \cup \partial E }[/math]. Each edge [math]\displaystyle{ e \in E_{0} }[/math] (interior edge) joins two interior vertices, each edge [math]\displaystyle{ e \in \partial E }[/math] (boundary edge) connects an interior vertex with a boundary vertex.

A [math]\displaystyle{ d }[/math]-regular tree with boundary is a tree, where all interior edges have length 1, all boundary edges have length [math]\displaystyle{ \leq 1 }[/math], and where all interior vertices have degree [math]\displaystyle{ d }[/math] and all boundary vertices degree 1. The set of interior vertices is not empty, i.e. [math]\displaystyle{ |V_{0}| \geq 1 }[/math].