Show that every graph with two or more nodes contains two nodes that have equal degrees.

Ramsey's theorem. Let \(G\) be a graph. A clique in \(G\) is a subgraph in which every two nodes are connected by an edge. An anti-clique, also called an independent set, is a subgraph in which every two nodes are not connected by an edge. Show that every graph with \(n\) nodes contains either a clique or an anti-clique with at least \(\frac{1}{2} \log _{2} n\) nodes.

Examine the following formal descriptions of sets so that you understand which members they contain. Write a short informal English description of each set. a. \(\\{1,3,5,7, \ldots\\}\) b. \(\\{\ldots,-4,-2,0,2,4, \ldots\\}\) c. \(\\{n \mid n=2 m\) for some \(m\) in \(\mathcal{N}\\}\) d. \(\\{n \mid n=2 m\) for some \(m\) in \(\mathcal{N}\), and \(n=3 k\) for some \(k\) in \(\mathcal{N}\\}\) e. \(\\{w \mid w\) is a string of os and 1 s and \(w\) equals the reverse of \(w\\}\) f. \(\\{n \mid n\) is an integer and \(n=n+1\\}\)

Let \(X\) be the set \(\\{1,2,3,4,5\\}\) and \(Y\) be the set \(\\{6,7,8,9,10\\}\). The unary function \(f: X \longrightarrow Y\) and the binary function $g: X \times Y \longrightarrow Y$ are described in the following tables. $$ \begin{aligned} &\begin{array}{c|c} n & f(n) \\ \hline 1 & 6 \\ 2 & 7 \\ 3 & 6 \\ 4 & 7 \\ 5 & 6 \end{array}\\\ &\begin{array}{c|ccccc} g & 6 & 7 & 8 & 9 & 10 \\ \hline 1 & 10 & 10 & 10 & 10 & 10 \\ 2 & 7 & 8 & 9 & 10 & 6 \\ 3 & 7 & 7 & 8 & 8 & 9 \\ 4 & 9 & 8 & 7 & 6 & 10 \\ 5 & 6 & 6 & 6 & 6 & 6 \end{array} \end{aligned} $$ a. What is the value of \(f(2)\) ? b. What are the range and domain of \(f ?\) c. What is the value of \(g(2,10)\) ? d. What are the range and domain of \(g\) ? e. What is the value of \(g(4, f(4))\) ?

If \(A\) has \(a\) elements and \(B\) has \(b\) elements, how many elements are in $A \times B$ ? Explain your answer.

Write formal descriptions of the following sets. a. The set containing the numbers 1,10 , and 100 b. The set containing all integers that are greater than 5 c. The set containing all natural numbers that are less than 5 d. The set containing the string aba e. The set containing the empty string f. The set containing nothing at all