Some basic Theorems about Graphs in Exercises: Part 16.

Join Medium with my referral link - applied.math.coding

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 fulfills deg(G) >/= ord(G) / 2 is connected.

Remember, ord(G) is the number of vertexes and deg(G) is the minimal degree among all its vertexes. The degree of a vertex is the number of its neighbors.

Solution:

To simplify notation let us define n := ord(G) and m := ceil(n/2) + 1. Thus m is one larger than deg(G). We start by picking an arbitrary vertex v_1. By assumption v_1 has at least n adjacent vertexes. So let us pick one and denote it by v_2. If deg(G) > 1, then…