MTH4140: Midterm 1 Practice 3

The statement (A) is false because if \(R\) is a relation on \(A\) then \(R\) is a subset of \(A\times A\) and consequently, \(R\times R\) is a subset of \(A\times A\times A\times A\) however, \(R\times R\) does not have to be equal to \(A\times A\times A\times A\).

The statement (B) is true. A transitive relation, like any other relation on \(S\), must be a subset of \(S\times S\).

The statement (C) is true. The set \(V\) is a relation on \(A\) because it contains ordered pairs of elements of \(A\) and as such \(V\subseteq A\times A\).

The statement (D) is false. A counter-example is \(Q=\{1,2\}\), \(P=\left\{(1,1),(2,2)\right\}\). Then \(P\) is a reflexive relation on \(Q\). However, \(Q\) is not a relation on \(P\) because \(Q\) is not a subset of \[P\times P=\left\{\left((1,1),(1,1)\right), \left((1,1),(2,2)\right), \left((2,2),(1,1)\right), \left((2,2),(2,2)\right)\right\}.\]

The statement (E) is false. If \(P\) is a relation on \(Q\) then \(P\subseteq Q\times Q\). The set \(P\times Q\) is a subset of \(Q\times Q\times Q\). However, for \(X\) to be a relation on \(Q\) the set \(X\) must be a subset of \(Q\times Q\).

We can take the set \( S \) to be the set consisting of the first \( 3 \) positive integers. Then we have \(S=\left\{1,2,3\right\}\). One non-surjective function can be defined as \( f:S\times S\to S \) as \( f(x,y)=1 \) for every \( (x,y)\in S\times S \). This means that \begin{eqnarray*}f(1,1)=1,\; f(1,2)=1,\; f(1,3)=1,\; f(2,1)=1,\; f(2,2)=1,\; f(2,3)=1,\; f(3,1)=1,\; f(3,2)=1,\; f(3,3)=1. \end{eqnarray*}

Let us denote the graphs from left to right by \( G_1=\left(V_1,E_1\right) \), \( G_2=\left(V_2,E_2\right) \), and \( G_3=\left(V_3,E_3\right) \). Let us define the sets of vertices by \begin{eqnarray*} V_1&=&\left\{B_1,B_2, B_3,B_4,B_5,B_6\right\},\newline V_2&=&\left\{E_1,E_2, E_3,E_4,E_5,E_6\right\},\newline V_3&=&\left\{R_1,R_2, R_3,R_4,R_5,R_6\right\} \end{eqnarray*} and define the sets of edges in such a way that the graph representations are given in the pictures below

\(\quad\) \(\quad\)

Observe that the graph \( G_{3} \) is bipartite since the vertices of even degree can be colored in green and the vertices of odd degree can be colored in red and no two vertices of the same color are connected with an edge. On the other hand, the other two graphs contain cycles of length three. These cycles are \( \left(B_1,B_2,B_3\right) \) and \( \left(E_1,E_2,E_3\right) \). Therefore the graph \( G_{3} \) is isomorphic to neither of \( G_{1} \) and \( G_{2} \). On the other hand the graphs \( G_{1} \) and \( G_{2} \) are isomorphic. It is easy to verify that the function \( f:V_{1}\to V_{2} \) defined by \( f\left(B_i\right)=E_i \) for \( i\in\{1,2,\dots, 6\} \) is a bijection and the vertices \( B_i \) and \( B_j \) are adjacent in \( G_{1} \) if and only if the vertices \( E_i \) and \( E_j \) are adjacent in \( G_2 \) for every \( i, j\in\{1,2,\dots, 6\} \).

Recall that a non-trivial graph is an Eulerian trail if and only if the number of vertices of odd degree is at most \( 2 \). Therefore the answers are the following:

For the first graph the answer is no. The graph has two vertices of degree 5 and two vertices of degree 3;

For the second graph the answer is yes;

For the third graph the answer is no. The graph has three vertices of degree five and one vertex of degree 3.

Let us denote \( \displaystyle P(n)\equiv \left\{a_n=\frac{8 \cdot 4^n-2\cdot \left(-2\right)^n }{6}\right\} \). We first obtain that \[ \displaystyle P(1)\equiv \left\{a_1=\frac{8 \cdot 4^1-2\cdot \left(-2\right)^1 }{6}\right\} \quad\mbox{and}\quad\displaystyle P(2)\equiv \left\{a_2=\frac{8 \cdot 4^2-2\cdot \left(-2\right)^2 }{6}\right\}\] hence \( P(1)\equiv T \) and \( P(2)\equiv T \).

We will now prove that for \( n\geq 3 \) the statements \( P(n-1) \) and \( P(n-2) \) imply \( P(n) \).

From \( a_n=2=2a_{n-1}+8a_{n-2} \) and from \( P(n-1) \) and \( P(n-2) \) we obtain: \begin{eqnarray*}a_n&=&2a_{n-1}+8a_{n-2}=2\frac{8 \cdot 4^{n-1}-2\cdot \left(-2\right)^{n-1} }{6} +6\frac{8 \cdot 4^{n-2}-2\cdot \left(-2\right)^{n-2} }{6}\newline &=&\frac{4^{n-2}\cdot 8 \cdot\left( 2\cdot 4+8\right) -2^{n-2}\cdot 2\cdot \left(-2\cdot 2+8\right) }{6} = \frac{8 \cdot 4^n-2\cdot \left(-2\right)^n }{6}. \end{eqnarray*} According to the principle of mathematical induction we obtain that \( \displaystyle a_n=\frac{4 \cdot 4^n-{ } \left(-2\right)^n }{3} \).

Let us determine the degree of an arbitrary vertex \( u=\left(a_1, \dots, a_{6}\right) \). Our first goal is to determine for which sequences \( w=\left(b_1, b_2, \dots, b_{6}\right) \) the number \( (a_1-b_1)\cdots (a_{6}-b_{6}) \) is not divisible by \( 7 \). Notice that the product is not divisible by \( 7 \) if and only if none of the terms \( (a_1-b_1) \), \( (a_2-b_2) \), \( \dots \), \( (a_n-b_n) \) is divisible by \( 7 \). For each integer \( x\in\{1,2,\dots, 43\} \) denote by \( f(x) \) the number of integers \( y \) from \( \{1,2,\dots, 43\} \) for which \( x-y \) is not divisible by \( 7 \). If \( x \) is equal to \( 1 \), then \( y \) must not belong to the set \( \{1, 8, 15, \dots, 43\} \). The last set has \( 7 \) elements. Therefore \( f(1)=43-7=36 \). Similarly, for every \( x\in\{1, 8, 15, \dots, 43\} \) we have \( f(x)=36 \). On the other hand, if \( x\not\in\{1,8,15,\dots, 43\} \), then there are exactly \( 6 \) numbers from \( \{1,2,\dots, 43\} \) that give the same remainder as \( x \) when divided by \( 7 \). Thus for \( x\not\in\{1,8,15,\dots, 43\} \) we have \( f(x)=43-6=37 \). The degree of the vertex \( u=\left(a_1, \dots, a_{6}\right) \) is equal to \[ d(u)=f\left(a_1\right)\cdot f\left(a_2\right)\cdots f\left(a_{6}\right).\] Hence if each of the numbers \( a_1 \), \( \dots \), \( a_{6} \) is in the set \( \{1, 8, 15, \dots, 43\} \) the degree of \( u \) is equal to \( 36^{6} \) which is an even number. However, if none of \( a_1 \), \( \dots \), \( a_{6} \) belongs to the set \( \{1, 8, 15, \dots, 43\} \) then the degree of \( u \) is \( d(u)=37^{6} \) which is an odd number. Since there are many vertices whose degree is odd, it is not possible to find a path that visits every edge exactly once.