Homework Help: Combinatorics: Finite Graph

1. Apr 23, 2015

Robben

1. The problem statement, all variables and given/known data

Show that any finite graph contains two vertices lying on the same number of edges.

2. Relevant equations

None

3. The attempt at a solution

I am confused how my book proved this.

Let G be a graph with n vertices $v_1, ..., v_n.$ Place $v_i$ in a pigeonhole labelled $m$ if it has exactly $m$ neighbours. The possible labels on the pigeonholes are $0,1,2,..., n-1$ so $n$ vertices are placed in $n$ pigeonholes. However, the pigeon-holes labelled $0$ and $n-1$ cannot both be occupied.

Why can't they both not be occupied? And what exactly do they mean by occupied?

2. Apr 23, 2015

ehild

An occupied pigeon-hole labelled by k contains the vertices having k neighbours.
If there are n vertices, and one of them has no neighbours, no other vertices are connected to it. What is the maximum number of edges from one vertex?
In a graph of n vertices, the maximum number of the edges from a vertex is n-1. If there is a vertex with n-1 neighbours, it means every vertex is connected to that one. Is there any vertex without neighbours then?

Last edited: Apr 24, 2015
3. Apr 24, 2015

epenguin

Never knew this nor occurred to me. Can you prove it by simple induction? I would like to see it done.

Seems to me if you draw a graph the first step is one edge between two vertices, and thereafter you can never add an edge in such a way that the theorem is violated. ?

4. Apr 24, 2015

ehild

My post was answer to the question of the OP, about occupancy of the "pigeonholes", and was not connected to the solution of the problem itself. For me, it is not quite clear what the sentence
means. Is it that there are at least two vertices with the same number of neighbours?

Last edited: Apr 24, 2015
5. Apr 24, 2015

epenguin

That's what I thought it meant.

6. Apr 24, 2015

Dick

I've also seen the problem stated as "Show every finite graph has two vertices with equal degree". So I think that interpretation is correct.

7. Apr 25, 2015

Robben

Can you elaborate on this, please? I have trouble understanding combinatorics without examples.

I've noticed, when I am studying combinatorics, that I have to re-read the questions many times (at least 15 times lol) for me to understand it, is that normal? I don't have that problem with my other classes.

8. Apr 25, 2015

ehild

With the "pigeonhole" method, you have to arrange N vertices in N-1 holes.

See picture. You have a connected graph, with N=5 vertices.

B and C both have one neighbour each. D and E both have two neighbours. A has 4 neighbours. Maximum number of edges connected to a vertex is 4.

If you add an isolated vertex, which is not connected to any other point, the graph consists of 6 vertices, but the maximum number of neighbours is still 4. The hole labelled by 5 is empty. So consider connected graphs only.

You have to put N vertices into N-1 holes. Is it possible with a single vertex in each hole?
Combinatorics needs a special way of thinking, For me, it is difficult , too. Make drawings, it helps!

9. Apr 25, 2015

haruspex

Frankly, the book's method is making an easy solution look hard.
Suppose every vertex can have a different degree. What's the least degree a vertex can have? What's the greatest degree a vertex can have if there are n vertices? If the are n different degrees in the graph, what are they? Is such a graph possible? In particular, can that minimum degree and that maximum degree coexist in one graph?

10. Apr 25, 2015

Robben

Thank you very much, that was very helpful!

Thank you!