Hello I really need help with this HW! Any help is welcome and extremely appreciated!



Prove or disprove, as appropriate, each of these statements. Use equation editor for mathematical symbols, formulas, predicates, equations, and so forth. You may use all the proof techniques we’ve used so far: direct proof, existential instantiation, generalizing from generic particular, counterexamples, contradiction, contraposition, etc., as well as basic algebra.


1. Among a set of two or more people, there must be a pair of people acquainted with the same number of people in the set. Assume that “acquaintanceship” is a symmetric relation; that is, if A is acquainted with B, then B is acquainted with A. (Hint: Use “acquaintanceship” to define a graph and prove something about the degrees of the vertices.)



3. For any integer n ≥ 2, the sum of n odd integers is odd if n is odd and even if n is even. (Strong induction.)

Calculate the following:



5. A graph has vertices of degree 1, 1, 4, 4, and 6. How many edges does the graph have?
Draw an example of a graph with these degrees.

1.
Let N the number of people in your set. Define the graph G with :
- N vertices, each one represents 1 people
- an edge exists between 2 vertices if and only if those 2 people are acquainted.

Think about the degree of each vertex : it is the number of people a given person is acquainted with.
So it may vary from 0 to N-1 (N possibilities).

Your problem is to prove that at least 2 vertices have same degree.
If it wasn't the case, then you should have all degrees from 0 to N-1 used (because N different values would be required for N vertices).
You can see it's impossible, since, then, one vertex would have degree zero, and one another would have degree N (which implies it is connected to the former).

3.
This seems more like a practise of writing induction than a real question, since the answer is quite obvious.
If you add up an even number of odd numbers, you can pair them 2 by 2, given a sum of even numbers : the result is even.
If you add up an odd number of odd numbers, then do the same, and 1 odd number remains : the result is odd.

5.
The number of edges in a graph is half the sum of all degrees of the vertices :
1+1+4+4+6 = 16
16/2 = 8
your graph has 8 edges.

Example :

A, B, C, D, E are the vertices.

Edges = { AC - BC - CD - CD - CE - CE - DE - DE }