| 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), so there cannot be an Euler circuit. | + | 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. Actually, this only holds for undirected graphs. But if a directed graph's corresponding undirected graph does not have an Euler circuit, then neither does the directed graph (the converse is not true, see <math>H_1</math> in Figure 4 on page 634). In this graph, vertices b and c both have odd degrees (7 and 5, respectively), so there cannot be an Euler circuit in the corresponding undirected graph. Therefore, the directed graph also does not have an Euler circuit. --[[User:Mkorb|Mkorb]] 19:21, 18 November 2008 (UTC) |
Revision as of 14:32, 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. Actually, this only holds for undirected graphs. But if a directed graph's corresponding undirected graph does not have an Euler circuit, then neither does the directed graph (the converse is not true, see $ H_1 $ in Figure 4 on page 634). In this graph, vertices b and c both have odd degrees (7 and 5, respectively), so there cannot be an Euler circuit in the corresponding undirected graph. Therefore, the directed graph also does not have an Euler circuit. --Mkorb 19:21, 18 November 2008 (UTC)
