908 views
1 votes
1 votes

The graph in the figure is a portion of the Shri Chakra.

Is it :

(1) a Planar graph ?

(2) a Hamiltonian graph ?

(3) an Eulerian graph ?

(A) 1 and 2

(B) 2 and 3

(C) 1 and 3

(D) 1, 2 and 3
 

2 Answers

1 votes
1 votes

(1)Planar Graph:-A graph G is planar if it can be drawn in the plane in such a way that no two edges meet each other except at a vertex to which they are incident.

This graph is a planar graph.Here no edges cross each other.

(2)Eulerian Graph:- A connected graph G is Eulerian if there is a closed trail which includes every edge of G,  such a trail is called an Eulerian trail.

If every vertex of G has even degree, then G is Eulerian.

In Given Graph every vertex has even degree.Hence it is Eulerian. 

(3)Hamiltonian Graph:-A connected graph G is Hamiltonian if there is a cycle which includes every vertex of G; such a cycle is called a Hamiltonian cycle.

There is no Hamilton cycle present in the graph.So given graph is not Hamiltonian graph.

Option(C)1 and 3 should be the correct choice. 

Reference:http://www.personal.kent.edu/~rmuhamma/GraphTheory/MyGraphTheory/planarity.htm

http://www.personal.kent.edu/~rmuhamma/GraphTheory/MyGraphTheory/eulerGraph.htm

Related questions

1 votes
1 votes
1 answer
1
sh!va asked Dec 3, 2016
1,261 views
G1 and G2 are two graphs as shown—(A) Both 01 and G2 are planar graphs(B) Both G1 and G2 are not planar graphs(C) GI is planar and G2 is not planar graph(D) G1 is not p...
2 votes
2 votes
2 answers
3
shivani2010 asked Jun 12, 2016
4,258 views
An undirected graph is Eulerian if and only if all vertices of G are of the sum of the degrees of all nodes isA. Same degreeB. ODD degreeC. Need not be ODDD. ...
0 votes
0 votes
1 answer
4
gmrishikumar asked Nov 30, 2018
852 views
All the places where I have read the Ham-Cycle problem, the graph used is directed. Is the problem of finding Ham-Cycle on an undirected graph also NP-Complete or not?