Write \(C(G)\) for “\(G\) is connected”, \(E(G)\) for “\(G\) has at least \(n\) edges”, where \(n\) is its number of vertices, and \(T(G)\) for “\(G\) is a tree”. The statement is \(\forall G\,\bigl(C(G)\to(E(G)\lor T(G))\bigr)\) . By Theorem 1.8, Theorem 1.4(e), and De Morgan’s law, its negation is

there is a connected graph with \(n\) vertices that has fewer than \(n\) edges and is not a tree.

The original statement is true. Let \(G\) be connected with \(n\) vertices. By Theorem 6.8 it has at least \(n-1\) edges. If it has at least \(n\) , the first alternative holds. Otherwise it has exactly \(n-1\) edges, and a connected graph with \(n-1\) edges is a tree by Theorem 6.14(b). So the negation is false.

Injective. If \(f(a_1)=f(a_2)\) , apply \(g\) : \(a_1=g(f(a_1))=g(f(a_2))=a_2\) . Surjective. For \(a\in A\) , the element \(b=f(a)\) satisfies \(g(b)=a\) . These are parts (c) and (d) of Theorem 2.8 applied to the composition \(g\circ f=\mathrm{id}_A\) , which is both injective and surjective.

Now let \(A\) and \(B\) be finite with the same number of elements. By Corollary 5.12 the injective function \(f:A\to B\) is also surjective, hence bijective, and the surjective function \(g:B\to A\) is also injective, hence bijective. By Theorem 2.9, \(f\) has an inverse \(f^{-1}\) . Composing \(g\circ f=\mathrm{id}_A\) on the right with \(f^{-1}\) gives \(g=f^{-1}\) . So \(g\) is the inverse of \(f\) , and then \(f\) is the inverse of \(g\) . Without finiteness the conclusion fails: on \(\mathbb N\) , take \(f(n)=n+1\) and \(g(n)=n-1\) for \(n\ge 1\) , \(g(0)=0\) .

Let \(P(n)\) be the statement \(\sum_{i=1}^{n}i\cdot i!=(n+1)!-1\) .

Base case: for \(n=1\) the left side is \(1\cdot 1!=1\) and the right side is \(2!-1=1\) .

Inductive step: let \(k\ge 1\) and assume \(P(k)\) . Then

where the first equality uses the induction hypothesis. This is \(P(k+1)\) .

By induction \(P(n)\) holds for all \(n\ge 1\) . The identity can also be seen without induction: \(i\cdot i!=(i+1)!-i!\) , and the sum telescopes.

Euclid’s algorithm: \(391=1\cdot 299+92\) , \(299=3\cdot 92+23\) , \(92=4\cdot 23+0\) . So \(\gcd(391,299)=23\) . Back-substituting,

so \(x=-3\) , \(y=4\) .

For the congruence \(299x\equiv 46\pmod{391}\) : \(d=\gcd(299,391)=23\) and \(23\mid 46\) , so by Theorem 4.16 there are solutions, forming \(23\) residue classes modulo \(391\) . Dividing by \(23\) gives \(13x\equiv 2\pmod{17}\) . The inverse of \(13\) modulo \(17\) is \(4\) , since \(13\cdot 4=52=3\cdot 17+1\) . Hence \(x\equiv 8\pmod{17}\) . The solutions are \(x\equiv 8,25,42,\dots\) , that is, \(x\equiv 8+17k\pmod{391}\) for \(k=0,1,\dots,22\) . Check: \(299\cdot 8=2392=6\cdot 391+46\) .

Bipartite? No. The vertices \(0,1,2\) are pairwise adjacent, since their differences are \(1\) , \(2\) , and \(1\) . A triangle is an odd cycle, so by Theorem 6.18 the graph is not bipartite.

Euler circuit? Yes. Each vertex \(i\) is adjacent to \(i\pm 1\) and \(i\pm 2\) modulo \(7\) , four different vertices, so every degree is \(4\) , which is even. The graph is connected, because it contains the cycle \(0,1,2,\dots,6,0\) . By Theorem 6.22 it has an Euler circuit.

Chromatic number. Four colours suffice: colour \(0,1,2,3,4,5,6\) with \(a,b,c,a,b,c,d\) . Vertices with the same colour are \(0\) and \(3\) , \(1\) and \(4\) , \(2\) and \(5\) , whose differences are \(3\) , not one of \(1,2,5,6\) ; so no edge joins equal colours. Three colours do not suffice: among any three vertices of the same colour no two could be adjacent, but any three of the seven vertices include two whose difference modulo \(7\) is \(1\) , \(2\) , \(5\) , or \(6\) , because three vertices pairwise at circular distance \(3\) would need \(3\cdot 3=9\) steps around a cycle of length \(7\) . So each colour is used at most twice, three colours cover at most \(6\) vertices, and \(\chi=4\) .

The argument proves that if \(a\mathrel R b\) then \(a=b\) . In other words, \(R\) is contained in the equality relation: it relates only equal elements. It does not prove the converse, that every element is related to itself. Equality on a set \(A\) is the relation \(\{(a,a):a\in A\}\) , and to conclude that \(R\) is that relation one needs both inclusions.

The claim is false. The empty relation on a nonempty set is symmetric and antisymmetric, both vacuously, and it is not equality. So is \(\{(1,1)\}\) on the set \(\{1,2\}\) .

What must be added is reflexivity. A relation that is reflexive, symmetric, and antisymmetric contains every pair \((a,a)\) by reflexivity and no other pair by the argument given, so it is the equality relation. The error is the one in Exercise 2.17 seen from the other side: a conditional property cannot produce pairs that are not already there.

Choose any two rows and any two columns, and consider the four lamps where they cross. A move on one of the two chosen rows switches exactly two of these four lamps; so does a move on one of the two chosen columns; a move on any other row or column switches none of them. So every move changes the number of lit lamps among the four by \(-2\) , \(0\) , or \(2\) , and the property “an even number of these four lamps are on” is an invariant. It holds at the start, when none are on, so by the invariant principle it holds in every reachable state, for every choice of two rows and two columns.

Suppose a state with exactly one lamp on were reachable. Choose the row and column of that lamp together with any other row and any other column. Among the four lamps at the crossings exactly one is on, an odd number. This contradicts the invariant. Hence the state is unreachable. A count of all cases agrees: the \(2^{8}\) combinations of row and column moves produce \(128\) different states, and the number of lamps lit in them is always one of \(0,4,6,8,10,12,16\) .