Discrete Mathematics Practice Test 8

1. The maximum number of edges in a bipartite graph on 14 vertices is ___________

2. The binary relation U = Φ (empty set) on a set A = {11, 23, 35} is _____

3. The rank of smallest equivalence relation on a set with 12 distinct elements is _______

4. An undirected graph has 8 vertices labelled 1, 2, ...,8 and 31 edges. Vertices 1, 3, 5, 7 have degree 8 and vertices 2, 4, 6, 8 have degree 7. What is the degree of vertex 8?

5. Let S be a set of n>0 elements. Let be the number B_r of binary relations on S and let B_f be the number of functions from S to S. The expression for B_r and B_f, in terms of n should be ____________

6. Determine the set of all integers a such that a ≡ 3 (mod 7) such that −21 ≤ x ≤ 21.

7. A graph is ______ if and only if it does not contain a subgraph homeomorphic to k₅ or k_3,3.

8. If each and every vertex in G has degree at most 23 then G can have a vertex colouring of __________

9. A partial order ≤ is defined on the set S = {x, b₁, b₂, … b_n, y} as x ≤ b_i for all i and b_i ≤ y for all i, where n ≥ 1. The number of total orders on the set S which contain the partial order ≤ is ______

10. G is a simple undirected graph and some vertices of G are of odd degree. Add a node n to G and make it adjacent to each odd degree vertex of G. The resultant graph is ______