in Graph Theory
896 views
0 votes
0 votes
$A)$ If a graph has closed Eularian walk, then it has an even number of edges

$B)$ If $G$ be a simple graph on $9$ vertices and the sum of all degrees in $G$ is atleast $27$, then $G$ has a vertex of degree atleast $4$.

Which Statement should be true?

Is it possible B) to be true?

And for A) I think "only if" is needed in place of "if" to be true
in Graph Theory
by
896 views

4 Comments

''min_degree * no of vertices >= 28 '' Does this mean that we are assuming all the vertices of the graph to have degree equal to the minimum degree?And what does that signify  ? Can someone please explain...
0
0
Here the sum of all the degrees is atleast 28 (it can't be 27 since sum of all degrees have to be even for a graph).

 If we assume that all the graph have minimum degree 3,then sum of the degrees will be (3*9)=27.Hence there has to be a vertex with degree 4.

This is nothing but an application of the extended pigeonhole principle.
0
0
ok,got it,thanks!!!
0
0

Please log in or register to answer this question.

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