MTH 4140: Midterm 1 Practice 1

Let \(c\in C\). Since \(h\) is onto, there exists \(a\in A\) such that \(h(a)=c\). This means that \(g(f(a))=c\), hence by taking \(b=f(a)\) we know that \(b\in B\) and \(g(b)=c\).

If \(f(1)=4\), there are \(4!\) such bijections. If \(f(1)=6\), there are \(4!\) more bijections, and if \(f(1)=8\), there are \(4\) bijections. Hence there is a total of \(3\cdot 4!=72\) such bijections.

A binary relation on \(A\) is any subset of \(A\times A\). Let \(R\) be the set of all reflexive binary relations on \(A\). Let \(S\) be the set of all symmetric relations on \(A\). We need to find \(|R\setminus S|=|R\setminus (S\cap R)|=|R|-|R\cap S|\). Each reflexive binary relation must contain all of the pairs \((1,1)\), \((2,2)\), \(\dots\), \((n,n)\). The total number of such relations is \( |R|=2^{n^2-n}\). A relation \(U\) is both reflexive and symmetric if \(\{(1,1),(2,2),\dots (n,n)\}\subseteq U\) and whenever \((i,j)\in U\) then \((j,i)\in U\). There are \(\frac{n(n-1)}2\) pairs \((i,j)\) with \(i < j\) and each relation from \(S\cap R\) is uniquely determined by the set of such pairs. Therefore \(|S\cap R|=2^{\frac{n(n-1)}2}\) and \[|R\setminus S|=2^{n(n-1)}-2^{\frac{n(n-1)}2}.\]

Let us denote by \( P(n) \) the following statement: \[ P(n)\equiv \left\{\mbox{ The following equality holds: }a_n=3^n+7^n.\right\}\] The statement \( P(0) \) is \( a_0=3^0+7^0=1+1=2 \) which is true since from the formulation of the problem we have that \( a_0=2 \). The statement \( P(1) \) is \( a_1=3^1+7^1=3+7=10 \) which is true since from the formulation we know that \( a_1=10 \). Assume that \( n\geq 1 \) and assume that all the statements \( P(0) \), \( P(1) \), \( \dots \), \( P(n) \) are true. We will now prove that the statement \( P(n+1) \) is true. We need to prove that \( a_{n+1}=3^{n+1}+7^{n+1} \). From the formulation of the problem we know that \( a_{n+1}=10a_n-21a_{n-1} \). Since \( P(n) \) is true we know that \( a_n=3^n+7^n \). Since \( P(n-1) \) is true we know that \( a_{n-1}=3^{n-1}+7^{n-1} \). Therefore \begin{eqnarray*}a_{n+1}&=&10a_n-21a_{n-1}=10\left(3^n+7^n\right)-21\left(3^{n-1}+7^{n-1}\right)\newline &=& 3^{n-1}\cdot \left(10\cdot 3-21\right)+7^{n-1}\left(10\cdot 7-21\right)=3^{n-1}\cdot 3^2+7^{n-1}\cdot 7^2=3^n+7^n. \end{eqnarray*} This completes the proof of \( P(n+1) \) and by the principle of mathematical induction we have proved that for each \( n\geq 0 \) we have \( a_n=3^n+7^n \).

The edges need to be drawn between the following pairs of vertices: \begin{eqnarray*} (1,2),\; (1,4),\; (2,3),\; (2,5),\; (3,4),\; (4,5). \end{eqnarray*}

This graph is \(K_{2,3}\) and the picture is shown in the figure below.

The first step in solving this problem is labeling the vertices of the graph. We will label the vertices using the letters of the English alphabet: \(A\), \(B\), \(C\), \(D\), \(E\), \(F\), and \(G\) as shown in the picture below.

In the complement of the graph the vertices are the same: \(A\), \(B\), \(C\), \(D\), \(E\), \(F\), and \(G\). However, each vertex in the complement must be adjacent to exactly those vertices to which it is not adjacent in the original graph. Thus \(A\) is adjacent to \(D\) only; \(B\) is adjacent to \(D\), \(E\), and \(F\); \(C\) is adjacent to \(F\); \(D\) is adjacent to \(F\), \(A\), and \(B\); \(E\) is adjacent to \(B\); \(F\) is adjacent to \(B\), \(C\), and \(D\); and \(G\) is not adjacent to any of the vertices. The complement is the graph whose edges are colored blue in the picture above.

Let us denote the graphs by \(G_1\), \(G_2\), and \(G_3\), from left to right. We will prove that \(G_1\) and \(G_3\) are isomorphic while \(G_2\) is not isomorphic to either of them. Let us denote by \(V_1\) and \(V_3\) the sets of vertices of \(G_1\) and \(G_3\) and let us label the sets as \begin{eqnarray*} V_1&=&\left\{A_1,A_2,A_3,A_4,A_5,A_6, A_7, A_8, A_9, A_{10}, A_{11}, A_{12}, A_{13}, A_{14}, A_{15}, A_{16}\right\},\newline V_3&=&\left\{B_1, B_2, B_3, B_4, B_5, B_6, B_7, B_8, B_9, B_{10}, B_{11}, B_{12}, B_{13}, B_{14}, B_{15}, B_{16}\right\} \end{eqnarray*} as shown in the pictures below.

The graph \(G_2\) has the cycle \((P, Q, R, S, T)\) of length \(5\), hence it cannot be bipartite. On the other hand, the graphs \(G_1\) and \(G_3\) are bipartite. We can paint in green the vertices of odd degree and in red the vertices of even degree. Observe that no two vertices of the same color are adjacent in either of the graphs \(G_1\) and \(G_3\).

We will now prove that \(G_1\) and \(G_3\) are isomorphic. Consider the function \(f:V_1\to V_3\) defined as \(f(A_i)=B_i\) for each \(i\in\{1,2,3,\dots, 16\}\). The function \(f\) is a bijection and direct verification shows that \(\left(A_i,A_j\right)\) is an edge in \(G_1\) if and only if \(\left(B_i, B_j\right)\) is an edge in \(G_3\) for each \(i,j\in\{1,2,3,4,5\}\).

The graph \(G\) is Eulerian hence every vertex has even degree. Assume that there is a cut edge between vertices \(u\) and \(v\). If the edge between \(u\) and \(v\) is erased, there are two connected components \(A\) and \(B\) such that \(u\in A\) and \(v\in B\). The degree of every vertex in \(A\) is even, except for \(u\), whose degree is odd (because the edge \(uv\) is removed). This is not possible, because the sum of degrees of all vertices in \(A\) must be even.

Let us consider the graph that has \(2^k\) vertices labeled using all possible sequences \(\left(a_1, a_2,\dots, a_k\right)\) of length \(k\) whose terms are from the set \(\{0,1\}\). Two vertices with labels \(\left(a_1, a_2,\dots, a_k\right)\) and \(\left(b_1, b_2, \dots, b_k\right)\) are connected with an edge if and only if the sequences differ in exactly one component. Since each vertex is labeled by a sequence with \(k\) terms, there are exactly \(k\) other sequences each of which differs in exactly one coordinate. Thus the degree of each vertex is \(k\).

We will now prove that the described graph is bipartite by showing one coloring of its vertices. For each vertex we first calculate the sum of its coordinates. If the sum is even, we paint the vertex is green. Otherwise, we paint it in red. In order to show that there is no edge between green vertices and no edge between red vertices it is sufficient to observe that if two vertices are neighbors then their sums of components differ by exactly \(1\). Hence, among every two neighbors one must have even sum and one must have odd sum of components. This means that no two neighbors can be of the same color.

The graph with \(6\) vertices can have at most \(15\) edges. If it has \(15\) edges, then the graph is complete, i.e. every two vertices are joined by an edge. It is easy to prove that if the edges of such graph are painted in red and green, then there must be a red triangle or a green triangle. This was Problem 4 on Homework 2.

Therefore \(e\leq 14\). We will now prove that \(e=14\) by providing one example of a graph that has \(6\) vertices, \(14\) edges, and whose edges can be colored in two colors without monochromatic triangle. We will start by observing that a complete graph with \(5\) vertices can have its edges painted in two colors as shown in the picture on the left. The graph is obtained from pentagon \(ABCDE\) in which diagonals are of one color and edges of the other.

We will now construct a graph \(G=(V,E)\) whose set of vertices is \(V=\left\{A,B,C,D,E,A_1\right\}\) and set of edges is formed by copying the edges and colors from the previous example of the pentagon with additional edges from vertex \(A_1\) defined in the following way: \(A_1\) is connected to each of \(\{B,C,D,E\}\) and for each \(X\in\{B,C,D,E\}\) the color of the edge \(A_1X\) is the same as the color of the edge \(AX\). This coloring guarantees that there are no monochromatic triangles. First of all, \(AA_1\) is not an edge and as such it cannot be a part of a triangle. Therefore each triangle must have its vertices in the set \(\{A,B,C,D,E\}\) or in the set \(\left\{A_1,B,C,D,E\right\}\). However, these two graphs are isomorphic to the complete \(K_5\) whose edges are painted in such a way that there are no monochromatic triangles.