Graph theory Basic terminology -1

 Definitions 

• More than one edge associated with a given pair of vertices, are referred to as parallel edges.

• A graph that has neither self-loops nor parallel edges is called a simple graph.

Königsberg Bridge Problem: The Königsberg bridge problem is perhaps the best-known example in graph theory. It was a long-standing problem until solved by Leonhard Euler (1707-1783) in 1736, by means of a graph.

Two islands, C and D, formed by the Pregel River in Königsberg (then the capital of East Prussia but now renamed Kaliningrad and in West Soviet Russia) were connected to each other and to the banks A and B with seven bridges. The problem was to start at any of the four land areas of the city, A, B, C, or D, walk over each of the seven bridges exactly once, and return to the starting point (without swimming across the river, of course).

Euler represented this situation by means of a graph. The vertices represent the land areas and the edges represent the bridges.

Euler proved that a solution for this problem does not exist. The Königsberg bridge problem is the same as the problem of drawing figures without lifting the pen from the paper and without retracing a line.

Utilities Problem: There are three houses H1 , H2 , and H3 , each to be connected to each of the three utilities—water (W), gas (G), and electricity (E)— by means of conduits. Is it possible to make such connections without any crossovers of the conduits?

This problem can be represented by a graph—the conduits are shown as edges while the houses and utility supply centers are vertices. the graph cannot be drawn in the plane without edges crossing over. Thus the answer to the problem is no.

A graph with a finite number of vertices as well as a finite number of edges is called a finite graph; otherwise, it is an infinite graph.

When a vertex v_i is an end vertex of some edge e_j , v_i and e_j are said to be incident with (on or to) each other.

Two nonparallel edges are said to be adjacent if they are incident on a common vertex.

Two vertices are said to be adjacent if they are the end vertices of the same edge

The number of edges incident on a vertex v_i , with self-loops counted twice, is called the degree, d(v_i ) of vertex v_i . The degree of a vertex is sometimes also referred to as its valency.

A graph in which all vertices are of equal degree is called a regular graph (or simply a regular).

A vertex having no incident edge is called an isolated vertex. In other words, isolated vertices are vertices with zero degree.

A vertex of degree one is called a pendant vertex or an end vertex.

A graph, without any edges, is called a null graph. In other words, every vertex in a null graph is an isolated vertex.

Resource: Graph Theory with Applications to Engineering & Computer Science NARSINGH DEO