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 ...continues

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) ...continues

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 hav ...continues

Eulerian and Non-Eulerian Graphs

Let G be a connected graph that is not Eulerian. Prove that it is possible to add a single vertex to G together with some edges from this new vertex to some old vertices so that the new graph is Eulerian. Please see attachment for background and hints.

Trees: Vertex; Cycle

Let G be a graph in which every vertex has degree 2. Is G necessarily a cycle? *Please see attachment for additional information. Thanks. Use words to describe solution process. Use math symbol editor like LateX, please no stuff like <=.

Discrete 47.3

3. Let d1,d2...dn be .... prove that d1...dn are degrees of the vertices. (see attachment for full question)

Graphs : Connectedness and Cycles

13. Let G be a connected graph with (please see the attachment). Prove that G contains exactly one cycle.

Graph Coloring Problem

Please use words to describe the solution process. Let G and H be the graphs in the following figure (see attachment): Please find x(G) and x(H).