#9 Graphs I

The degree sum is \(2+2+3+3+4=14\). Each edge is counted twice, so there are \(14/2=7\) edges.

The degree sum is \(3\), which is odd. But the degree sum of any graph is \(2E\), hence even. Such a graph does not exist.

We choose two vertices from \(8\). Therefore the number of edges is \(\binom{8}{2}=28\).

A path on \(6\) vertices has \(5\) edges, so its degree sum is \(10\). A cycle on \(6\) vertices has \(6\) edges, so its degree sum is \(12\).

Build the acquaintance graph. Each acquaintance pair contributes \(1\) to each of two people, hence \(2\) to the total sum. Therefore the sum of all stated numbers is twice the number of acquaintance pairs and is even.

The sum of all degrees is \(2E\), so it is even. The sum of degrees of even-degree vertices is even. Hence the sum of degrees of odd-degree vertices is also even. A sum of an odd number of odd numbers would be odd, so the number of such vertices is even.

The degree sum is \(36\). It is twice the number of edges, so there are \(36/2=18\) edges.

Each edge is obtained by choosing one vertex from the first part and one from the second. Thus there are \(4\cdot7=28\) edges.

The minimum is \(10-1=9\). It is achieved by a path on \(10\) vertices. Fewer edges are impossible because each new vertex needs at least one edge to join the connected part already built.

A tree on \(n\) vertices has exactly \(n-1\) edges. For \(n=15\), this gives \(14\) edges.

In a simple graph, there is at most one edge between two vertices. The maximum number of edges is in the complete graph \(K_8\), which has \(\binom{8}{2}=28\) edges. Therefore \(29\) edges are impossible.

If there is a person who knows all \(5\) others, then every other person knows at least that person. Thus no person can have \(0\) acquaintances. Therefore the degree set \(0,1,2,3,4,5\) is impossible.

Degrees can be \(0,1,\ldots,2n-1\). However, degrees \(0\) and \(2n-1\) cannot occur together: if someone knows everyone, then nobody has \(0\) acquaintances. Thus at most \(2n-1\) different degree values are available. There are \(2n\) people, so by the pigeonhole principle two degrees are equal.

If the graph has no cycles, each connected component is a tree. If the component sizes are \(n_1,\ldots,n_k\), then the number of edges is \((n_1-1)+\cdots+(n_k-1)=n-k\le n-1\). Thus an acyclic graph has at most \(n-1\) edges. If there are at least \(n\) edges, a cycle must exist.

Suppose there is a cycle. Remove one edge of this cycle. Its endpoints are still connected by the rest of the cycle, so the graph remains connected. We get a connected graph on \(n\) vertices with \(n-2\) edges, impossible because a connected graph has at least \(n-1\) edges. Hence there are no cycles.

Consider a longest simple path in the tree. Let one endpoint be \(v\). If \(v\) had a neighbor outside the path, the path could be extended, contradiction. If \(v\) had a neighbor on the path other than the nearest one, a cycle would appear, impossible in a tree. Thus \(v\) has exactly one neighbor, degree \(1\). The same holds for the other endpoint.

If the graph is disconnected, its vertices split into at least two components. One component has at most \(3\) vertices. Inside such a component, any vertex can be connected to at most \(2\) other vertices, so its degree is at most \(2\). This contradicts the condition that all degrees are at least \(3\).

Each edge is incident to exactly one vertex in the part of size \(5\). Therefore the sum of degrees in this part is \(20\). The average degree is \(20/5=4\). Hence at least one vertex has degree at least \(4\).

There are \(\binom{7}{2}=21\) games, hence \(21\) wins in total. The average number of wins per player is \(21/7=3\), so someone won at least \(3\) games. Similarly, there are \(21\) losses in total, the average number of losses is \(3\), so someone lost at least \(3\) games.

If the graph is disconnected, take a component. If its size is at most \(6\), every vertex in it has degree at most \(5\), contradiction. Thus every component must have at least \(7\) vertices. But two such components would contain at least \(14\) vertices, more than \(11\). Therefore there cannot be more than one component, and the graph is connected.

Choose a vertex \(v\). It has at least \(5\) neighbors. If two of these neighbors are adjacent, then together with \(v\) they form a triangle. If there are no edges among the neighbors of \(v\), then each such neighbor is adjacent to \(v\) and can be adjacent only to the three vertices that are neither \(v\) nor neighbors of \(v\). Its degree is then at most \(1+3=4\), contradicting minimum degree \(5\). Hence a triangle exists.

Let \(L\) be the number of leaves and \(T\) the number of degree \(3\) vertices. Then \(L+T=12\). The tree has \(11\) edges, so the degree sum is \(22\). Hence \(L+3T=22\). Subtracting the first equation gives \(2T=10\), so \(T=5\) and \(L=7\).

Since the number of edges equals the number of vertices, the graph contains a cycle. Take any edge of this cycle. If it is removed, its endpoints are still connected by the rest of the cycle. All other connections remain, so the graph stays connected.

Choose a person \(A\). Among the other \(5\) people, by the pigeonhole principle there are either \(3\) who know \(A\), or \(3\) who do not know \(A\). First suppose \(A\) knows \(B,C,D\). If among \(B,C,D\) there is an acquaintance pair, say \(B\) and \(C\), then \(A,B,C\) are three mutual acquaintances. If there is no acquaintance pair among \(B,C,D\), then \(B,C,D\) are three mutual strangers. The second case, with three people not acquainted with \(A\), is analogous: if among them there is a non-acquaintance pair, it together with \(A\) gives three mutual strangers; if not, those three are mutual acquaintances.