Show that any graph which contains a Hamilton cycle has a co

Show that any graph which contains a Hamilton cycle has a covering by two even subgraphs.

(Covering is a family of subgraphs of G)

Solution

A graph is said to be simple if it has no loops and parallel edges. A graph with possible loops and parallel edges is also called a multigraph. • A graph is said to be finite if its both vertex set and edge set are finite and assume all graphs are finite. • The graph with empty vertex set (and hence empty edge set) is called the null graph. • A graph is said to be trivial if it has only one vertex. All other graphs are said to be nontrivial. • A graph is called an empty graph if it does not contains any edge. • A complete graph is a simple that every pair of vertices are adjacent. A complete graph with n vertices is denoted by Kn. • A graph G is said to be bipartite if its vertex set V (G) can be partitioned into two disjoint parts X and Y such that every edge has one end-vertex in X and one in Y ; such a partition {X, Y } is called a bipartition of G, and such bipartite graph is denoted by G[X, Y ]. • A bipartite graph G[X, Y ] is called a complete bipartite graph if every vertex in X is joined to every vertex in Y.

; we denote G[X, Y ] by Km,n if |X| = m and |Y | = n

A Hamilton path of a graph G is a path that uses every vertex of G. A closed Hamilton path is called a HAMILTON CYCLE.

Definition of Subgraphs: • A graph H is called a subgraph of a graph G if V (H) subset and equal to V (G), E(H) subset & equal to E(G), and EndH : E(H) M2(V (H)) is the restriction of EndG : E(G) M2(V (G)) to E(H). We then say that G contains H or H is contained in G, and we write H subset & equal to G or G anti subset & equal to H. • A copy of a graph H in a graph G is a subgraph of G which is isomorphic to H. Such a subgraph is also reffered to as H subgraph of G.

A maximal connected subgraph of a graph G is called a connected component of G. The number of connected components of G is denoted by c(G).