Selena Matthews
Homework 7
August 11, 2013

6. What is the size of the largest induced Kn in Figure 6.9?
A complete graph on n vertices is Kn n vertices v1, v2, . . . , vn with an edge for each pair of distinct vertices

a. P3 no pair of vertices
b. not complete
c. not complete
d. K2 or C2
e. C5 not complete

Largest induced Kn is K2.

10. What can you say about a five vertex simple graph in which every vertex has degree four?

Five vertices *4 degrees = 20 edges

V = {1, 2, 3, 4, 5}
E = {(1,2), (1,3), (1,4), (1,5), (2,1), (2,3), (2,4), (2,5),
3,1, 3,2, 3,4, 3,5, 4,1, 4,2, 4,3, 4,5,
(5,1), (5,2), (5,3), (5,4)} I can say:
1. The simple graph is complete because all pairs of end points are joined by an edge.
2. I can say that it is not a tree because it contains a cycle.
3. That it is connected but undirected.
4. Adding all the degrees 4+4+4+4+4 for odd vertices and even degrees provides an even amount of edges =20.

14. Are there graphs with v vertices and v-1 edges and no cycles that are not trees? No
Give a proof to justify your answer.

Let G be a graph with v vertices and e edges
Let G1, G2, G3…,Gk be G's connected components
Let vi be the number of vertices of Gi
Let ei be the number of edges of Gi

Prove G has e = v-1 and no cycles but is not a tree
A tree T has v vertices and v-1 edges
T=(V,E)
v=V and vi=Vi v-1=E ei=E∩Vi2
Induce that ei=vi-1. A tree has v vertices and v-1 edges. vi=v-1 so E=ei+k= (vi-1)+k=(vi)=v-1

There must exist an i such that ei=vi but with no cycles vi=v and ei=e≥vi

Gi=ei > v-1
So a graph with connected components without cycles and without being a tree has more than v-1 edges.

2. Show that a finite graph is connected if and only if it has a spanning tree.

If G is a simple graph, then T is a spanning tree of G.
T is a subgraph of G and is a tree and contains every vertex V of G.
Let G be a graph containing a spanning tree (T).
T = a connected graph with vertex set V(G).
V(G) contains G which is a spanning sub graph that is connected. Every pair of vertices in G are connected because there is a path between them and T.

If G is connected, it has a spanning tree.
If G is a tree then it must have a spanning tree.
If G is connected and not a tree, then it has a cycle.
If G is a simple connected graph then it has no simple circuits and G is a spanning tree.
Remove edges from G until you cannot remove anymore without it being disconnected.
An edge is a cut-edge if and only if it can’t be removed without the graph becoming disconnected.

V(G) is still connected.
V(G) has no cycles.
A connected graph with no cycles is a tree.
Thus, G is connected and has a spanning tree.
Therefore, a graph is connected if and only if it has a spanning tree.

4. Draw all rooted trees on 6 vertices with four leaf vertices. If you would like to label the vertices (as we did in the graph in Figure 6.10), that is fine, but don’t give two different ways of labeling or drawing the same tree.

6. Create a breadth first search tree centered at vertex 12 for the graph in Figure 6.8 and use it to compute the distance of each vertex from vertex 12. Give the breadth first number for each vertex.

12 is the source d(12)=0 Q=12 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | d | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | 0 | π | / | / | / | / | / | / | / | / | / | / | / | / | I1: dequeue 12 enqueue 1, 2, 9 & 11 | d | 1 | 1 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | 1 | ∞ | 1 | 0 | π | 12 | 12 | / | / | / | / | / | / | 12 | / | 12 | / | I2: dequeue 1, 2, 9 & 11: enqueue 3, 7, 8, &10 | d | 1 | 1 | 2 | ∞ | ∞ | ∞ | 2 | 2 | 1 | 2 | 1 | 0 | π | 12 | 12 | 2 | / | / | / | 11 | 9 | 12 | 2 | 12 | / | I3: dequeue 3, 7, 8, &10 enqueue 4,5,6 | d | 1 | 1 | 2 | 3 | 3 | 3 | 2 | 2 | 1 | 2 | 1 | 0 | π | 12 | 12 | 2 | 3 | 7 | 8 | 11 | 9 | 12 | 2 | 12 | / |
Queue: 12-1-2-9-11-3-10-7-8-4-5-6
1. (12,1)
2. (12,2)
3. (12,2,3) 4. (12,2,3,4)
5. (12,11,7,5)
6. (12,9,8,6)
7. (12,11,7)
8. (12,9,8)
9. (12,9)
10. (12,2,10)
11. (12,11)

8. The depth of a vertex in a rooted tree is defined to be the number of edges on the (unique) path to the root. The height of a rooted tree is the maximum of the depths of its vertices. A binary tree is complete if it is full and all its leaves have the same depth. How many vertices does a complete binary tree of height 1 have? height 2? height d? (Proof required for height d.)

1. Let T be a complete binary tree with a height of 1. If T has a height of 1 then T has 2h+1 – 1 vertices=21+1 – 1=22 – 1=4-1=3 total vertices 2. Let T be a complete binary tree with a height of 2. If T has a height of 2 then T has 2h+1 – 1 vertices=22+1 – 1=23 – 1=8-1=7 total vertices 3. Let T be a complete binary tree and let h be the height of T or number of levels. Find how many total vertices does T with height d have? If T has a height of d then the amount of leaves at height d is 2d.
Let d=0 then 20=1 let d=1 then 21=2
Let d=2 then 22=4
Total levels = 1+2+4… or
T=20level 0+21level 1+22level 2… +2d-1level d T=20level 0+21level 1+22level 2… +2d-1level d proves to be a geometric series for 2d-1+2d=2d+1-1 Height 0 = 1 Height 1 = 2 + 1 = 3 Height 2 = 4 +2 +1 = 7 Level d = 2d+1-1
Let d=0 then 20+1-1=21-1=2-1=1
Let d=1 then 21+1-1=22-1=4-1=3 Height d: 2d+1 – 1=2d+1 – 1

T=2d+1-12-1=2d+1-11 =2d+1-1 total vertices for T with a height of d.

10. As defined in problem 8 a binary tree is complete if it is full and all its leaves have the same depth. A vertex that is not a leaf vertex is called an internal vertex. What is the relationship between the number I on the internal vertices and the number L of leaf vertices in a complete binary?

Let V be vertices, I be internal vertices and L be leaves.
Base case is T with 1 vertex. A tree of height h has L=2h leaves.
A tree with 1 vertex has a height of 0. L=20=L=1
A tree with 1 vertex and height of 0 has 2h-12-1=20-12-1=0
Base case of T with 1 vertex has 1L and 0I.

Assume it is true for all T and T consists of T1 and T2 and leaves of T1 and T2 consists of L1 and L2 and internal vertices of I1 and I2.
Let L(T) be the total leaves of T and I(T) be the total internal vertices of T.
LT=L(T1)+L(T2) and IT=I(T1)+IT2+1
Induction:
LT1=I(T1)+1 and LT2=I(T2)+1
LT=I(T1)+1+IT2+1=I(T1)+IT2+2
LT=IT+1
The relationship between the number I internal vertices and the number L leaf vertices in a complete binary is
L(T) the number of leaves of a complete binary tree T, is 1 more than I(T), the number of internal vertices of T.

2. For each graph in figure 6.25, either explain where the graph does not have a Eulerian trail or find it. a. has more than 3 vertices with a odd degree which prevents a trail from being completed using all edges at least once. b. (1,2)(2,3)(3,4)(4,2)(2,5)(5,4)(4,1)(1,5) c. (1,4)(4,5)(5,3)(3,2)(2,5)(5,1)(1,2) d. has more than 3 vertices with a odd degree which prevents a trail from being completed using all edges at least once.

6. The hypercube graph Qn has it’s vertex set the n – tuples of zeros and ones.
Two of these vertices are adjacent if and only if they are different in one position. The name hypercube comes from the fact that Q3 can be drawn in 3-D space as a cube.
For what values of n is the hypercube Qn Eulerian?

The n-dimensional hypercube Qn has 2n vertices and n2{n−1} edges.
Let n be 3 for Qn and 2n=23=8 vertices n2(n-1)=323-1=12edges
8/4= 2Q2 12/4=3 edges per vertex.
Q3 is not Eulerian.

Let n+1 be an even number 4 for Qn. Q3+1=4
2n=24=16 vertices n2(n-1)=424-1=32edges
Q4 is Eulerian.

A graph is Eulerian if and only if it is connected and every vertex has even degree.
Euler’s Formula. A hypercube with even values for n of Qn is Eulerian.

8. Find an example of a graph that has a Hamiltonian cycle but no Eulerian circuit and a graph that has a Eulerian circuit but no Hamiltonian cycle.

Hamiltonian cycle but no Eulerian circuit

Eulerian circuit but no Hamiltonian cycle

12. Which of the graph in figure 6.26 satisfy the hypotheses of Dirac’s theorem?
Every graph G with at least 3 vertices and at least a degree of v/2 has a Hamilton cycle.
a. 5 ≥ 3 true minimum degree 3(G) ≥ 5/2 true
b. 5 ≥ 3 true minimum degree 2(G) ≥ 5/2 not true
c. 9 ≥ 3 true minimum degree 2(G) ≥ 9/2 not true
d. 9 ≥ 3 true minimum degree 2(G) ≥ 9/2 not true a satisfies Dirac’s theorem.

Of Ore’s theorem?
Every graph G with n ≥ 3 vertices such that the sum of x,y of nonadjacent vertices is at least v.
a. v=5 true 3+3=6 true
b. v=5 true 2+3=5 true
c. v=9 true 2+2=4 not true
d. v=9 true 2+3=5 not true a and b satisfy Ore’s theorem.

Which have Hamiltonian cycles?

a. has a Hamiltonian cycle
b. has a Hamiltonian cycle