## 티스토리 뷰

Comp Sci/Algorithms

### Proof - Euler Trail Theorem (1)

jeongtaebang 2017.12.22 10:00

An Euler trail is a walk that uses every edge of a graph exactly once.

An Euler circuit is a circuit that uses every edge of a graph exactly once.

Euler trail with same endpoints is a Euler circuit.

Here are some examples:   Let be a finite connected graph and denote the number of vertices that have odd degrees.

Prove that G has a Euler trail if and only if .

First, by the Handshake Theorem, we can narrow down our range of :

An arbitrary can have . We will now try to show that some subset of , those that have Euler trails,  have .

Proof( ) : We know such that includes all edges of exactly once.

Case 1 : has endpoints It has middle vertices (vertices that are not endpoints).

By definition of a middle vertex, the trail does not end at , i.e. if it enters it has to leave it through

an edge.

Therefore, we can easily see that has an even degree.

Now consider . They may appear in multiple times but but each time they do so, they have a pair                 of edges entering and leaving them, EXCEPT when they are endpoints. In this case there's only

one edge leaving , the start of , and only one entering .

Hence have one more edge entering and one more edge leaving, respectively. , so the claim holds in this direction.

Case 2 : has endpoints , so we have an Eulerian cycle that starts and ends at .

For every vertex other than , edges in leave it and every time they enter . has an even degree.

Consider . When it appears in not as the start/end point of the cycle, same things happens to it as .

As the 종점 of the cycle, an edge leaves in the beginning and enters it at the end. has an even degree

as well. , so the claim holds in this direction.

Contrapositives rule out the possibility of Euler trails in graphs with more than 2 odd degrees.

Proof( ) : See Proof - Euler Trail Theorem (2)

Generalize to a trail :

Consider a trail in any graph. If we see the trail as a subgraph on its own, this is an Euler trail. Then we can apply the Euler Trail Theorem to learn something about the degree of vertices in the trail.

#### 'Comp Sci > Algorithms' 카테고리의 다른 글

 [Math] Permutations, Combinations, and Multiplication  (0) 2018.06.19 2017.12.23 2017.12.22 2017.12.21 2017.11.28 2017.11.26
댓글
• Component of subgraph G' partition G' because components by definition are maximally connected 2017.12.23 17:03 신고
• Need to revise conclusion

Finite connected simple graphs:
1) r = 0 <=> euler circuit exists
2) r = 2 <=> euler trail exists
2018.07.05 17:15 신고
댓글쓰기 폼
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
1,080
Today
0
Yesterday
1
링크
TAG more
«   2019/07   »
1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30 31
글 보관함