그래프 이론

1. For each set of integers shown below, draw a simple graph(no self-loops or parallel edges) having the indicated degrees or tell why you can`t

a) 2, 2, 3, 2, 2, 3

b) 1, 1, 2, 3, 4

simple graph를 그릴 수가 없다.
왜냐하면, odd degrees의 vertices의 수가 even이 되어야 하는데 그 조건을 만족하지 않는다.

c) 1, 2, 3, 3, 5

역시 simple graph를 그릴 수가 없다. 이유는 위와 동일하며, 만약 simple graph가 되기 위해서는 마지막 integer 5의 degree가 성립하기 위해서 self-loop나 parallel edge가 생겨야만 한다.

d) 1, 1, 2, 2, 4

2. Show that if self-loops and parallel edges are permitted then for any set of n, positive integers whose sum is even, there exists a graph whose n vertices have the indicated degrees

[answer] any set of positive integers =
위 any set of positive integers의 vertex를 라 하고, degree를 라 하자.
그러면 위에 해당하는 vertex에 대한 set of…(생략)

3. Given an undirected, connected graph G, show that it is always possible to find a circuit which traverses each edge exactly twice, once in each direction. Show such a circuit on the graph below