Given an example of fallacy. State the necessary and sufficient conditions for a graph to have Euler path and Euler circuit.

Question

Bipin Tiwari · Accepted Answer

Definition of Fallacy an idea or belief that is false but many people think is true Examples of Fallacy in a sentence Having money makes you happy is a fallacy because happiness has nothing to do with wealth. While the business plan sounds good on paper, it is built on the fallacy that people will pay thirty dollars to see a movie. Eulerian Path is a path in graph that visits every edge exactly once. Eulerian Circuit is an Eulerian Path which starts and ends on the same vertex. Necessary and sufficient conditions for Euler paths Euler circuit if and only if it has exactly two vertices of odd degree. Proof: (ONLY IF) Assume the graph has an Euler path but not a circuit. Notice that every time the path passes through a vertex, it contributes 2 to the degree of the vertex (1 when it enters, 1 when it leaves). Obviously the first and the last vertices will have odd degree and all the other vertices - even degree. (IF) Assume exactly two vertices, u and v, have odd degree. If we connect these two vertices, then every vertex will have even degree. By Theorem 1, there is an Euler circuit in such a graph. If we remove the added edge {u,v} from this circuit, we will get an Euler path for the original graph. End of proof Necessary and sufficient conditions for Euler circuits Obviously a non-connected graph cannot have an Euler path unless it has isolated vertices. Theorem 1. A connected multigraph has an Euler circuit if and only if each of its vertices has even degree. Why “only if”: Assume the graph has an Euler circuit. Observe that every time the circuit passes through a vertex, it contributes 2 to the vertex’s degree, since the circuit enters via an edge incident with this vertex and leaves via another such edge.

Given an example of fallacy. State the necessary and sufficient conditions for a graph to have Euler path and Euler circuit.

Leave your Answer:

Hits Counter

Question

Given an example of fallacy. State the necessary and sufficient conditions for a graph to have Euler path and Euler circuit.

Leave your Answer: