Can Any Finite Graph Have Vertices with Unique Edge Counts?

[Robben]

Homework Statement

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

Homework Equations

None

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?

 

[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?

 

[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. ?

 

[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

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

means. Is it that there are at least two vertices with the same number of neighbours?

 

[epenguin]

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?

That's what I thought it meant.

 

[Dick]

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?

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.

 

[Robben]

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?

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.

 

[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!

 

[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?

 

[Robben]

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.

View attachment 82527

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.
View attachment 82528
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!

Thank you very much, that was very helpful!

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?

Thank you!