Fundamentals of Graph

Question

1. Prove that Y is a simple graph on n vertices, then Y contains at most $\frac{n(n-1)}{2}$ edges.
   
2. Prove the following claim: in every simple graph Y on at least two vertices, we can always find two distinct vertices v, w such that deg(v) = deg(w).

Can someone help me with these graph related questions? I am really struggling on it.

Answer 1

1) Notice that edges correspond to unordered pairs of vertices $(v_i,v_j)$. In a simple graph there are no multiple edges between the same vertices or loops from a vertex to itself. So the question is, how many unordered pairs of vertices can we find in a graph with $n$ vertices, and the answer is well known: ${n \choose 2} = \frac{n(n-1)}{2}$.

2) Suppose we have a graph on $n$ vertices where the degrees of all vertices are distinct. As $0\leq \operatorname{deg}(v) \leq n-1$, and as all degrees in our graph are distinct, we have that the set $$ \{ \operatorname{deg}(v_1), \operatorname{deg}(v_2),\ldots, \operatorname{deg}(v_n) \} = \{0,1,\ldots, n-1\}. $$ However, this means we have a vertex of degree $0$ (not connected to any other vertex) and one vertex having degree $n-1$, i.e., connected to all vertices. This is a contradiction and so in all simple graphs we have two vertices with the same degree.

Answer 2

Here are a couple of hints.

For $1,$ how many pairs of vertices are there? For $2,$ if the graph has $n>2$ vertices, and they all have different degrees, what exactly are those degrees? Now find a contradiction.

Answer 3

1. If $Y$ is a simple graph on the vertices $\lbrace1, \ldots,n\rbrace$, then we can form $Y$ by removing a bunch of edges from $K_n$. All you need to do is convince yourself that $K_n$ has exactly $\frac{n(n - 1)}{2}$ vertices. There are a bunch of ways of doing it, most simply by noting that this expression is $\binom {n}{2}$, the number of unordered pairs of elements from a set of $n$ elements.

2. Use Pigeonhole principle. A simple graph on $n$ vertices can only be adjacent to up to $n - 1$ vertices. If you remove the (at most one) degree $0$ vertecies, then the remaining graph on at least $n - 1$ vertices has only $n - 2$ possible valencies. So, pigeonhole principle means that two adjacencies must be the same.