Basic Doubt

Question

Statement :

"Every Euler Graph is a simple graph"

 

Please comment whether it is true always or need not to be.

( My concern is whether multi edge or self loop is allowed in euler graph or not i. e non-simple graph allowed or not )

Comments

whether multi edge or self loop is allowed in euler graph or not

it can allow !

Note all multi edge graphs which are euler are not euler graph when they simplified !

But all multiedge graphs which are hamilton are should be hamilton graph when they simplified !

---

@Shaik Masthan 

How to simplify the graph ?

doesn't it change the graph itself ?

and why this is valid that graph was euler but now its not ? ( how can we change the graph ? coz after simplifying ,its not our original graph we argued on right )

( as pet made easy solution given multigraph is euler and if multigraph allowed then yes it is as all vertices are even degree )

---

why you are simplifying ?

Don't simplify incase of finding Euler graphs or not , but you can simplify in case of finding Hamilton graph or not.

more about euler graphs https://en.wikipedia.org/wiki/Eulerian_path#Definition

note that, in euler graphs, a vertex may visit more than one time but edge never visit more than once !

---

you simplified it in previous comments that why asked how and why simplify.

yes it cleared my doubt of multi edge are allowed. but i didn't seen this "simplify graph" thing before.

In which type of questions it is useful ?

---

ya, after you commented as " How to simplify the graph " then i understood my words confuses you !

In which type of questions it is useful ?

Hamilton graphs. read my previous comments clearly.

 

Note all multi edge graphs which are euler are not euler graph when they simplified !

But all multiedge graphs which are hamilton are should be hamilton graph when they simplified !

So, Don't simplify incase of finding Euler graphs or not , but you can simplify in case of finding Hamilton graph or not.

i hope it's clear right Now.

---

So if they give a multigraph and stated to find whether it is Hamiltonian or not then should i simplify it 1st before checking ?

---

yes, that makes your work easier !

---

Brother, now i got ur whole point.

1. Converting euler graph into simple may or may not preserve the eulerian property But Hamiltonian does.

2. Hence, converting in case of Hamiltonian make things easier as it does not have any "sufficient" check for graph to be Hamiltonian.


any reference or link where i can find how to exactly convert ?

or its just a process of removing multiedges if present between two nodes ?

 

@Shaik Masthan 

thanx :)

---

simply remove the parallel edges and self loops, then it is simple graph only !