perplexus.info :: Logic : Same Degree Vertices

Same Degree Vertices (Posted on 2008-08-21)

Define a finite graph (V,E) where V is a finite, non-empty set and
E is a subset of { {a,b} | a,b in V and a ≠ b }.

If c in V, we define


   E(c) = { {a,c} in E | a in V }

   V(c) = { a in V | {a,c} in E }

   d(c) = |E(c)| = |V(c)|

Prove for any finite graph (V,E), with |V| > 1, that
there exists a,b in V such that a ≠ b and d(a) = d(b).

Note:

   V is the set of vertices of the graph.

   E is the set of edges of the graph.

   E(c) is the set of edges incident to vertex c.

   V(c) is the set of vertices adjacent to vertex c.

   d(c) is the degree of vertex c.

Submitted by Bractals

Rating: 4.0000 (1 votes)

Solution: (Hide)

If the proposition is false, then the degree of the vertex is different for each vertex in V.
Let n = |V|. We can therefore label the vertices in V such that
0 ≤ d(a₁) < d(a₂) < . . . < d(a_n) (1)
Clearly, d(a_n) < n. This and inequality (1) imply
d(a_i) = i-1 for i = 1, 2, . . . , n
d(a_n) = n-1 implies that a₁ is in V(a_n).
But, this contradicts that d(a₁) = 0.

Therefore, the proposition is true.

Comments: ( You must be logged in to post comments.)

	Subject	Author	Date
	solution	Paul	2008-08-22 22:07:58

Please log in:

Login:
Password:
Remember me:

Sign up! \| Forgot password

Search:

Search body:

Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (19)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:


perplexus dot info