A graph has $ 30$ vertices, $ 105$ edges and $ 4822$ unordered edge pairs whose endpoints are disjoint. Find the maximal possible difference of degrees of two vertices in this graph.
Problem
Source:
Tags: LaTeX, combinatorics unsolved, combinatorics
17.04.2008 20:03
anonymous1173 wrote: A graph has $ 30$ vertices, $ 105$ edges and $ 4822$ unordered edge pairs whose endpoints are disjoint. Find the maximal possible difference of degrees of two vertices in this graph. the question you posted is most probably $ wrong$ or else my proof is although i cant see anything wrong let $ a_{i}$ for $ i$ $ =$ $ 1$ to $ 30$ denote degrees of the $ 30$ points $ 105$ edges $ \Longrightarrow$ total pairs of edges $ =$ $ \binom{105}{2}$ $ =$ $ 5460$ therefore number of pair of edges withcommon endpoint $ =$ $ 5460$ $ -$ $ 4822$ $ =$ $ 638$ which is also equal to $ \sum_{i = 1}^{30} \binom{a_{i}}{2}$ also $ \sum_{i = 1}^{30}a_{i}$ $ =$ $ 105*2$ $ =$ $ 210$ from that we get $ \sum_{i = 1}^{30}a_{i}^{2}$ $ =$ $ 2*638$ $ -$ $ 210$ $ =$ $ 1066$ therefore $ \sum_{1 \le i < j \le 30 }^{}(a_{i}^{2} + a_{j}^{2})$ $ =$ $ 29*\sum_{i = 1}^{30}a_{i}^{2}$ $ =$ $ 1066*29$ $ =$ $ 30914$ $ 2*\sum_{1 \le i < j \le 30 }^{}a_{i}a_{j}$ $ =$ $ ( \sum_{i = 1}^{30}a_{i} )^{2}$ $ -$ $ \sum_{i = 1}^{30}a_{i}^{2}$ $ =$ $ 210^{2}$ $ -$ $ 1066$ $ =$ $ 43034$ thus $ \sum_{1 \le i < j \le 30 }^{}(a_{i}^{2}$ $ +$ $ a_{j}^{2})$ $ -$ $ 2*\sum_{1 \le i < j \le 30 }^{}a_{i}a_{j}$ $ =$ $ \sum_{1 \le i < j \le 30}^{} (a_{i} - a_{j})^{2}$ $ =$ $ 30914$ $ -$ $ 43034$ $ <$ $ 0$ a contradiction
17.04.2008 20:52
$ \sum \binom{a_i}{2} = 638$ and $ \sum a_i = 210$ give $ \sum a_i^2 = 2\cdot 638 + 210$, not $ 2\cdot 638 - 210$. As a result you'll get $ \sum_{1 \leq i < j \leq 30} (a_i - a_j)^2 = 480$. Some LaTeX suggestions: (1) it's much more attractive to use \cdot instead of * for multiplication in LaTeX, and (2) there's no reason to put so many dollar signs -- an entire equation can be surrounded by dollar signs, you don't need to do the left half, equals sign and right half separately. This will make many of your equations look nicer. If you have a really big equation (or several equations), you should learn how to use the align* environment. (It's in the wiki LaTeX guide.)
18.04.2008 06:58
JBL wrote: $ \sum \binom{a_i}{2} = 638$ and $ \sum a_i = 210$ give $ \sum a_i^2 = 2\cdot 638 + 210$, not $ 2\cdot 638 - 210$. As a result you'll get $ \sum_{1 \leq i < j \leq 30} (a_i - a_j)^2 = 480$. Some LaTeX suggestions: (1) it's much more attractive to use \cdot instead of * for multiplication in LaTeX, and (2) there's no reason to put so many dollar signs -- an entire equation can be surrounded by dollar signs, you don't need to do the left half, equals sign and right half separately. This will make many of your equations look nicer. If you have a really big equation (or several equations), you should learn how to use the align* environment. (It's in the wiki LaTeX guide.) thanks for pointing out the misstake so is the answer 7??? for i was able to establisha bond for difference to be less thasn or equal to 7
18.04.2008 17:42
anonymous1173 wrote:
a result of another silly mistake that i got the bond to be 7 before able to show $ \le 5$ couldn,t contruct graph help would be a livesaver
25.03.2012 04:04
This will help you.\[\sum_{i=1}^{30}(a_i-7)^2=16\]