# Tag Info

3

By Vizing’s theorem there exists a proper edge-coloring of the graph in 10 colors. So there exist 5 colors coloring at least $(100\cdot 9/2)\cdot 5/10=225$ edges. The graph with these edges has maximal vertex degree at most 5.

3

I know that 1 and 15, 2 and 14, 3 and 13, 2 and 14, 1 and 15, 6 and 10, 7 and 9 and 8 and 8 make 16. So let those be the holes. In other words, take the $8$ holes $$\{1,15\}, \{2, 14\}, \{3, 13\}, \{4, 12\}, \{5, 11\}, \{6, 10\}, \{7, 9\}, \{8\}$$ As long as there is only one pigeon in each hole, then all pigeons are different (requirement (i)), and none ...

1

Suppose it is not true for some $n$, and a set of numbers $x_{1}\leq...\leq x_{n+1}$ for which $\sum^{n+1}_{i=1}x_{i}=2n$. Let $$m=\min\{|\sum_{j\in J}x_{j}-\sum_{i\not\in J}x_{i}|:J\subset\{1,...,n+1\}\}>0$$ be the smallest difference the two sets can have, note $m$ is even, and let $J_{m}$ be such that $$\sum_{j\in J}x_{j}-\sum_{i\not\in J}x_{i}=m$$ ...

1

What you are trying to prove is in fact false: The graph consisting of $10$ copies of $K_{10}$ is simple, $9$-regular and has $100$ vertices. Any subgraph with maximum degree $5$ contains at most $6$ vertices from each copy of $K_{10}$, and hence at most $15$ edges from each copy of $K_{10}$, and hence at most $150$ edges in total. Edit: As pointed out in ...

Only top voted, non community-wiki answers of a minimum length are eligible