Question

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

Answer 1

Yes, If graph G contain two distinct paths from vertex a to vertex b then G has a cycle.

Step-by-step explanation:

• Let assume G is finite simple graph and then every vertex of G has at least 2.
• Then assume p be an simple path of minimal length in G. i.e., p = a₁, a₂, a₃,...,  
• If degree (a₁) ≥2, then it supposed to have at least one another edge {b, a₁} having a₁ as vertex.
• If b is vertices of simple path p then sub path from a₁ to b and concatenated to form a cycle.
• Otherwise if b is not vertices of simple path then path b, a₁, a₂, a₃,.. , is a .
• Simple path that whose length is greater than simple path p, which shows the length is maximal by contradicting.
• So by above if the vertices has degree greater than 2 or above then it form the cycle.

 

To learn more ...

1. State Dirac’s and Ore’s Theorem in graph theory,

brainly.in/question/1755851.