Coverings

In a graph G a set g of edges is said to cover G if every vertex in G is incident on at least one edge in g. A set of edges that covers a graph G is called edge covering, covering subgraph, or simply a covering of G.

e.g. a graph G is trivially its own covering. Spanning tree in a connected graph (or a spanning forest in an unconnected graph) is another covering. Hamiltonian circuit (if it exists) in a graph is also a covering.

Detection of Planarity

Every subgraph of a planar graph is planar and that every graph which has non-planar graph is also non-planar. A disconnected graph is planar iff each of its components is planar. Similarly, in a separable graph, planarity of each block can be considered independently. Thus, a separable graph is planar iff each of its block is planar. Thus, we need to consider only non-separable connected graph.

Colouring of Graphs

A colouring of a graph G is an assignment of colours to its vertices such that no adjacent vertices have the same colour. A given graph can be properly coloured in many different ways. We are finding the minimum number of colours with which a given graph can be properly coloured.

e.g., There are three different proper colouring of a graph with different number of colours.