I'm working on a triangle partitioning problem, and I'm trying to find and prove some properties of specific triangulations. The triangulations I'm dealing with are constrained delaunay triangulations in which every constraint is at least an edge (there are no single vertex constraints). Here is an example of such a triangulation:The red lines represent edge constraints and the blue lines represent the unconstrained edges produced to create the triangulation. Notice how all vertices are in some edge constraint and that there will never be a vertex that is not connected to a constrained edge.Now let us create a graph from this triangulation. Every triangle is a vertex, and edges are defined by $(v_1,v_2)$ where $v_1$ and $v_2$ are triangles that share an unconstrained edge. Notice that every vertex in this graph has degree at most 3.My problem is that I want to say something about the number of 3 degree vertices in such a graph. I believe that at least half the vertices have less than degree 3 (just from a hunch) but I have no idea how to go about proving such a thing. What I'm asking is, what is the upper bound of the ratio degree 3 vertices to total vertices in a triangulation with these properties.EDIT: I found this on the delaunay triangulation wikipedia page. Delaunay triangulations have $O(n^{d/2})$ simplicies, so a planar DT would have $O(n)$ triangles where $n$ is the number of vertices. This isn't the same as the set of constrained delaunay triangulations we're working with, but it seems to suggest that there could be a relationship degree-3 triangles and the total number of triangles.http://www.sciencedirect.com/science/article/pii/092577219500013Y
Number of 3-edge triangles in a planar triangulation
graph theory;graph algorithms;delaunay triangulation