| Line 8: | Line 8: | ||
---- | ---- | ||
| − | There is no Euler circuit. An Euler circuit must contain every ''edge'' in the graph. Theorem 1 says that there is an Euler circuit if and only if each vertex has an even degree. But in this graph, vertices b and c both have odd degrees (7 and 5, respectively).--[[User:Mkorb|Mkorb]] 19:21, 18 November 2008 (UTC) | + | There is no Euler circuit. An Euler circuit must contain every ''edge'' in the graph. Theorem 1 says that there is an Euler circuit if and only if each vertex has an even degree (and I believe that only holds for undirected graphs, see <math>H_1</math> in Figure 4 on page 634). But in this graph, vertices b and c both have odd degrees (7 and 5, respectively), so there cannot be an Euler circuit. I don't know about the Euler path though.--[[User:Mkorb|Mkorb]] 19:21, 18 November 2008 (UTC) |
Revision as of 14:24, 18 November 2008
The Euler Circuit should be : a -> b -> d -> c-> e-> f ->a.
But for Euler Path, I am still trying to figure out.
The closest I got was one of the path was not covered between C and B. This graph has 2 vertex with odd degree, it should have an Euler path.
-ngw
I agree with the Euler Circuit from ngw. There are others though, a > b > f > d > c > e > a for instance. --rtabchou
There is no Euler circuit. An Euler circuit must contain every edge in the graph. Theorem 1 says that there is an Euler circuit if and only if each vertex has an even degree (and I believe that only holds for undirected graphs, see $ H_1 $ in Figure 4 on page 634). But in this graph, vertices b and c both have odd degrees (7 and 5, respectively), so there cannot be an Euler circuit. I don't know about the Euler path though.--Mkorb 19:21, 18 November 2008 (UTC)
