MTH4140 Home

# MTH 4140: Midterm 1 Practice 1

Problem 1

Assume that $$A$$, $$B$$, and $$C$$ are three sets and that $$f:A\to B$$ and $$g:B\to C$$ are two functions. Consider the function $$h:A\to C$$ defined as $$h(x)=g(f(x))$$ for all $$x\in A$$. Prove that if $$h$$ is onto then $$g$$ is onto as well.

Problem 2

Determine the number of bijections $$f:\{1,2,3,4,5\}\to\{4,5,6,7,8\}$$ such that $$f(1)$$ is even.

Problem 3

Let $$A=\{1,2,3,\dots, n\}$$. Determine the number of binary relations on the set $$A$$ that are reflexive but not symmetric.

Problem 4

Assume that the sequence $$a_n$$ is defined as $$a_0=2$$, $$a_1=10$$, and $$a_{n+2}=10a_{n+1}-21a_n$$ for every $$n\geq 0$$. Use the principle of mathematical induction to prove that $$a_n=3^n+7^n$$ for all $$n\geq 0$$.

Problem 5

Let $$V=\{1,2,3,4,5\}$$ be the vertices of a graph $$G$$. Two vertices $$i$$ and $$j$$ are joined by an edge if and only if $$i+j$$ is odd. Draw the graph $$G$$.

Problem 6

Determine the complement of the graph shown in the picture below. Problem 7

Determine which of the pairs of graphs below are isomorphic. Problem 8

Assume that the graph $$G$$ can be drawn without lifting pen from the paper and without tracing the same line twice and that this drawing can be made in such a way that it starts and ends in the same vertex. Prove that the graph $$G$$ does not have cut edges.

Problem 9

Prove that for each integer $$k\geq 2$$ there exists a bipartite graph $$G$$ with $$2^k$$ vertices whose each vertex has degree $$k$$.

Problem 10

A graph is called red-green triangle free if all of its edges can be painted in red and green in such a way that there is neither a red triangle nor a green triangle. What is the maximal number $$e$$ of edges that a red-green triangle free graph can have, if the graph has $$6$$ vertices?