search
Log In
1 vote
280 views
A simple graph is one in which there are no self loops and each pair of distinct vertices is connected by at most one edge. Show that any finite simple graph has at least two vertices with the same degree.
in Graph Theory
retagged by
280 views

2 Answers

2 votes
 
Best answer

Proof by contradiction:

In a simple graph of $n$ vertices,

Minimum degree possible $=0$

Maximum degree possible $ = n-1$

Assume that all $n$ vertices of the graph have different degrees. It implies that we enumerate all vertices uniquely with their degrees from $0$ to $n-1$. But since vertices with degrees $0$ and $n - 1$ cannot co-exist in a simple graph, it results in a contradiction.

Therefore, atleast two vertices must have the same degree.


selected by
1 vote
Lets take graph with 3 vertices $v _1, v_2, v_3$. now assign different degree to each vertex for $d( v _1)=0$ , $d(v _2)=1$ ,$d(v_3)= 2$, now use handshaking theorem that is $2*edge=$ $sum$ $of$ $the$ $degree$ $of$ $each$ $ vertex$ , which also conclude that sum of degrees of vertices should be even

now , add each  degree of each vertices that is $ \Rightarrow 0+1+2 =3$ (which is not even) to make this even u have to make $v _3=1$ , or $v _1=1,v _2=1,v _3=2$  or   $v  _1=0,v _2=0,v _3=0$ and so many possibilities

now if some people argue for $v _1=2,v _2=3,v _3=5$ , for that we cant tale such example for 3 vertices graph because simple graph(no loop and parallel edges) is given.

edited by
0
You only proved for a $3$ vertex graph.

Related questions

14 votes
2 answers
1
1.3k views
A complete graph on $n$ vertices is an undirected graph in which every pair of distinct vertices is connected by an edge. A simple path in a graph is one in which no vertex is repeated. Let $G$ be a complete graph on $10$ vertices. Let $u$, $v$, $ w$ be three distinct vertices in $G$. How many simple paths are there from $u$ to $v$ going through $w$?
asked May 23, 2016 in Graph Theory jothee 1.3k views
17 votes
3 answers
2
1.9k views
A simple graph is one in which there are no self-loops and each pair of distinct vertices is connected by at most one edge. Let $G$ be a simple graph on $8$ vertices such that there is a vertex of degree $1$, a vertex of degree $2$, a vertex of degree $3$, a vertex of degree ... of degree $6$ and a vertex of degree $7$. Which of the following can be the degree of the last vertex? $3$ $0$ $5$ $4$
asked May 23, 2016 in Graph Theory jothee 1.9k views
1 vote
1 answer
3
205 views
When a user submits a query, a search engine does the following. For every webpage that has been visited by the search engine, it computes a score indicating how relevant that page is to the query. Finally, it reports the pages with the top k scores on the screen, ... by the user. A good data structure for accumulating the scores and ranking them is: a queue a heap a stack a binary search tree
asked May 23, 2016 in DS jothee 205 views
2 votes
1 answer
4
429 views
Your final exams are over and you are catching up on watching sports on TV. You have a schedule of interesting matches coming up all over the world during the next week. You hate to start or stop watching a match midway, so your aim is to watch ... on dynamic programming to compute the maximum number of complete matches you can watch next week. Analyze the worse-case complexity of your algorithm.
asked Jun 8, 2016 in Algorithms Arjun 429 views
...