CSCI 190 Exam III
Exam III
1)(8 points) Prove that a tree with n vertices has n-1 edges for .
Pf: base case: for n=1, there are no edges since a simple graph has no loops. Therefore there are n-1=1-1=0 edges.
Assume P(n) is true. Show p(n+1) is tree.
To show p(n+1), remove a leaf from a tree of n+1 vertices. A leaf exist by a previous theorem. Note that a leaf is of degree 1, only one edge is removed. Then the remaining graph is still connected (since the paths between other vertices are not affected by the removal) and has no cycles. Thus it is still a tree. Thus there are n-1 edges by p(n). Then the original graph has n-1+1=n edges.
2)Define a relation R on the set of integer Z as follows: iff is even.
a)(6 points) Show R is an equivalence relation. You may assumed the fact that even + even =even and od + odd is even)
Pf: a) (refelxsive) aRa since a+a =2a is even
b)(symmetric) If aRb, the a+b is even. But a+b=b+a. Thus bRa.
c)(transitive) Suppose aRb and bRc. Then a+b and b+c is even. NTS a+c is even. Note that a+b is even and b+c is even, so their sum (a+b)+(b+c)=a+2b+c is even. Thus a+c=(a+2b+c)+(-2b) is even.
d)(2 points) Find the equivalence class of 1.
This is the set of odd integers
3)(3 points each) Define a relation R on { 2, 4, 8,16 } as follows: iff
a)Construct a Hasse diagram
b)Find all the maximal elements. 16
c)Is R a lattice? Justify your answer. Yes, lub of (a,b)=max(a,b) and glb (a,b)=min(a,b)
4)(4 points) Find the strongly connected components. {a},{b},{c,d,e}. C, d, and e are in the same component since there is a directed path between any two vertices in the set using the cycle.
5)(3 points each) Below is a graph G. (a) Is G Eulerian? (b) Is G Hamiltonian? (For a, You do not need to prove that your answers are correct, but you should show some work to support your answers.)
a)Yes, since all the vertices are even: abcdecfbefa
b)Yes, abcdefa
6)(6 points) Determine if the following graphs are isomorphic. If they are, then you must construct an isomorphism.
Yes, let f(a)=A, f(b)=B, f(c)+c, f(d)=D. abAB abAB bcBC acAC, adAD
CSCI 190 Exam III Part II
7)( 2 points each)
a)Find the maximum number of leaves in a rooted binary tree of height 10.210
b)Find the number of leaves of a full rooted binary tree with 20 internal vertices.2(2)+1-20=21
c)Find the number of connected components of a connected simple graph.
Only one component when a graph is connected.
d)Determine if the degree sequence 5, 4, 3, 2,1 is possible for a simple graph.
Impossible. The sum of degree is 15, not even.
8)(2 points each) Let A ={1,2,3} and R ={(1,2), (1,3) ,(2,3)}, S={(1,3),(2,3),(3,1)} be relations on A
a)Construct a matrix of R.
Solution:
b)Use the matrix in a) to determine if R transitive.
Yes,
Thus R is transitive since its Boolean powers do not create new zeros.
c)Is R antisymmetric?
Yes. If an off diagonal entry is 1, then its corresponding entry that is diagonally across is 0
d)Find {(1,1),(2,2),(1,3)}
9)(6 points) Let G be a simple graph with 10 vertices. (there is no significance to this number 10. ) Use pigeon hole principle to show there are at least two vertices of the same degree. (hint: there are two cases. The first case is that there is a vertex of degree 9. The second case is there are no vertices of degree 9)
Pf: case1) If there is a vertex of degree 9, then this vertex is adjacent to all other vertices. Thus there are no vertices of degree0. So there are 9 possible degrees (1, 2, …9 ) with 10 vertices. Thus by the pigeon hole principle (pigeon are vertices and pigeon holes are degrees), at least two vertices are of the same degree.
Case 2) There are no vertices of degree 9. Then there are 9 possible degrees (0, 1,2, --8) with 10 vertices. Thus by the pigeon hole principle (pigeon are vertices and pigeon holes are degrees), at least two vertices are of the same degree.
10)(6 points) Show that if every vertex of a connected graph G has degree 2 or more, then G must contain a circuit. (hint: use a contradiction proof)
Pf: Suppose there are no cycles. Then since G is connected, it is a tree. By a tree with n≥2 has at least two leaves, contradiction. Thus G has a cycle.