Some basic Theorems about Graphs in Exercises: Part 17.
This story belongs to a contiguous series with the aim to list some of the basic theorems of graph theory. It is intentionally written in form of exercises to invite the reader having a ‘learning experience by doing’. In this sense it is not important to have solved any of these exercises but it is important to have tried them for a couple of minutes.
As usually in this series, all graphs are assumed to be simple, undirected and finite, except otherwise mentioned.
Problem 1:
A graph
G
that fulfillsdeg(v) + deg(w) >/= ord(G)
for all distinct non-adjacent vertexesv
,w
, is connected.
Remember ord(G)
is the number of vertexes and deg(x)
the number of all adjacent vertexes of x
.
Solution:
Assume to the contrary that G
is not connected. Then we can split G
into the graphs H
and R
such that no vertex of H
can be connected to a vertex in R
. On the one hand we have
ord(G) = ord(H) + ord(R)