document.write( "Question 1176930: A binary tree is a connected graph with no cycles, where each vertex has a degree less than or equal to 3. What is the maximum number of vertices of degree one that a binary tree with 15 vertices can have? \n" ); document.write( "
Algebra.Com's Answer #805114 by greenestamps(13200)\"\" \"About 
You can put this solution on YOUR website!


\n" ); document.write( "The degree of each vertex is either 1 or 2.

\n" ); document.write( "A total of 15 vertices with a maximum number of vertices of degree 1 means a minimum number of vertices of degree 2.

\n" ); document.write( "The total of 15 vertices will be reached fastest if the vertices in the first few levels of the tree all have degree 2.

\n" ); document.write( "Instead of trying to draw binary trees in typed text, I'll make a chart of the numbers of vertices of degree 1 or 2, and the total numbers of vertices, for increasing numbers of levels.
\r\n" );
document.write( "   # of   vertices of  vertices of   total\r\n" );
document.write( "  levels   degree 2     degree 1    vertices\r\n" );
document.write( " --------------------------------------------\r\n" );
document.write( "     1        0            1           1\r\n" );
document.write( "     2        1            2           3\r\n" );
document.write( "     3        3            4           7\r\n" );
document.write( "     4        7            8          15

\n" ); document.write( "So the maximum number of vertices of degree 1 in a binary tree with 15 vertices is 8.

\n" ); document.write( " \n" ); document.write( "
\n" );