Binary Tree Induction

# Recall that a binary tree can be defined recursively as * A Binary Tree is either empty * or A Binary Tree consists of a node with a left and right child both of which are Binary Trees. The degree of a node in a tree is equal to 0 if both children are empty, 1 if one of the children are empty, and 2 of both children are not empty. Use induction to show that the number of nodes in a binary tree is equal to one more than the sum of the degrees of the nodes in a binary tree.

Subgraphs

Let G be a complete graph on n vertices. Please calculate how many spanning and induced subgroups G has... (see attachment)

Graphs : Connectedness, Vertices and Edges

11. Let G be a graph with n>= 2 vertices. a) Prove that if G has at least (n-1) + 1 edges the G is connected. ( 2 ) b) Show that the result in (a) is best possible; that is, for each n>= 2, prove there is a graph with (n- 1) ( 2 ) edges that is not connected.

Graphs : Eulerian Trails

1. We noticed that a graph with more than two vertices of odd degree cannot have an Eulerian trail... (please see the attached file).

Euler Tour : Dominoes

2. A domino is a 2x1 rectangular piece of wood. On each half of the domino is a number, denoted by dots. In the figure, we show all C(5,2) = 10 dominoes we can make where the numbers on the dominoes are all pairs of values chosen from {1,2,3,4,5} (we do not include dominoes where the two numbers are the same). Notice that we have arranged the ten dominoes in a ring so that, where two dominoes meet, they show the same number. For what values of n  2 is it possible to form a domino ring using all () dominoes formed by taking all pairs of values from {1, 2,3,. . . , n}? Prove your answer. Note: In a conventional box of dominoes, there are also dominoes both of whose squares have the same num... click for more