The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
177 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.
asked in Graph Theory by Veteran (116k points)
retagged by | 177 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.

answered by Active (1.8k points)
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.
answered by Active (5k points)
edited by
0
You only proved for a $3$ vertex graph.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,434 questions
53,630 answers
186,007 comments
70,898 users