Some basic Theorems about Graphs in Exercises: Part 6.

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:

Show that if K_{r,s} is regular then r = s.

K_{r,s} is a graph that consists of two distinct vertex sets X, Y, where the size of X is r and of Y is s. Moreover, the edges of this graph are given by

{ {v,w} : v in X, w in Y } 

In other words, all vertexes in X are connected to all vertexes in Y by an edge.

A regular graph is a graph of which every vertex has the same degree (number of neighbors).