Explanation : EulerCircuits: An Euler circuit is a circuit that uses every edge of a graph
exactly once. HamiltonCircuit: Hamilton circuit, is a graph cycle (i.e., closed-loop) through a graph that visits each node exactly once Bipartite Graph: A bipartite graph, also called a bigraph, is a set of graph vertices decomposed into two disjoint sets such that no two graph vertices within the same set are adjacent. A bipartite graph is a special case of a k-partite graph with k=2. From the above definitions, we can see that (d) is false. So the answer is (D).
Explanation : A simple graph G=(V,E) is called bipartite if its vertex set can be partitioned into two
disjoint subsets V=V1⋃V2, such that every edge has the form e=(a,b) where aϵV1 and bϵV2.
Bipartite graphs are equivalent to two-colorable graphs.
1. Assign Red color to the source vertex (putting into set V1).
2. Color all the neighbours with Black color (putting into set V2).
3. Color all neighbour’s neighbour with Red color (putting into set V1).
4. This way, assign color to all vertices such that it satisfies all the constraints of m way coloring problem where m = 2.
5. While assigning colors, if we find a neighbour which is colored with same color as current vertex, then the graph cannot be colored with 2 colors (ie., graph is not Bipartite).
So answer is option (C).
Explanation : Caterpillar tree: In graph theory, a caterpillar is a tree in which all the vertices are within distance 1 of a central path.
Theorem: All caterpillars are graceful.
So, (a), (b) and (c) are graceful.