Question

suppose a graph contains two distinct paths from a vertex a to vertex b .show that G has a cycle.

Answer 1

Given : a graph contains two distinct paths from a vertex a to another vertex b.

To show : given graph G has a cycle.

Step-by-step explanation:

SIn this problem since G has two vertex and two edges between them so G is connected graph. To describe this problrm we have to know -

• Cycle : Existance a cycle in a graph means there exixts a closed walk. That is begening vertex and end vertex of a walk are not distinct.

Thereore we need Eular graph concept to prove the requirments.

• Eular graph : A connected graph is called Eular graph if there exist a closed walk in which every edge occurs exactly once.

Now we have to know a theorem-

• Theorem : A connected graph is called Eular graph iff every vertex has even order.

In our graph G we have two vertices and two edges. Therefore degree of each vertes is 2 that is degree of vertex a=2, degree of vertex b=2, which is even.

So by the above theorem we can concldude G is a Eular graph, that is G contains a closed walk, that is a cycle.