Introduction to graph theory

Theorem 1.1 G가 n개의 vertices를 갖는 multigraph 라고 하면 각 vertex의 degree(vertex에 연결된 edge의 갯수)의 합은 G의 edge 갯수의 2배와 같다.


Corollary 1.2 odd vertices(degree가 홀수인 vertices) 의 갯수는 짝수이다.

• complete graph : graph의 모든 vertices 가 서로 연결되어 있는 graph. Kn 으로 표시. 여기서 n은 order로서 vertices의 수를 의미
• null graph : 그래프 G가 있을때 E(G) =0 인 그래프. 즉 edge가 하나도 없는 그래프. Nn으로 표시. 여기서 n은 vertex 수
• walk : vertex와 edge의 번갈아가면서 나오는 sequence. v0 e0 v1 e1 v2... vn. 이때 길이는 edge의 갯수
• trail : walk 중에 edge가 두개 이상 반복이 안된 walk.
• path : walk 중에 vertex가 두개 이상 반복이 안된 walk. path는 반드시 trail이다. 그러나 역은 반드시 성립하는 것은 아니다.
• distance from x to w : vertex x 에서 vertex w 까지의 최단 path 길이. d(x,w) 로 표현한다.
• closed : vertex u에서 시작해서 vertex v로 끝나는 walk가 있을때 u = v 이면 이는 closed 되어 있다고 한다.
• circuit : closed walk 중에 edge가 반복이 안된 walk.
• cycle : circuit 중에 vertex가 반복이 안된 circuit. Cn 은 n 개의 vertex를 갖는 cycle을 의미
• connected : multigraph G의 모든 vertex가 path로 연결되어 있다면 G는 connected 되었다고 한다.
• isomorphic : 두 그래프 G와 H가 같을때 isomorphic이라 한다. 정확히 이야기 하자면 isomorphism 이라고 불리는 함수 f (그래프 G에서 H로의 mapping(vertex to vertex) 함수로서 그래프 G의 adjacency(두 vertices의 연결)를 유지하게 하는 함수)  가 존재할 때, 두 그래프는 isomorphic 하다라고 한다. isomorphism은 하나 이상이 될 수 있다.
• induced subgraph : H가 G의 induced subgraph 라고 한다면 v(H) 가 v(G)의 subset이고 이 G 안에서 subset 사이에 존재하는 edge가 모두 H에 있음을 의미한다. 

Isomorphism Testing Problem : 두 그래프 G와 H가 isomorphic한가를 판단하는 문제.

--chapter 3--

• bipartite : order(vertex의 갯수)가 최소 2 이상인 그래프 중 vertex가 두 그룹으로 나뉘고 모든 edge가 각 두 그룹의 vertex를 join 하게 할때 이를 bipartite 라고 한다.
• partite sets : bipartite graph에서 두 subgroup(두 vertex set)을 partite set이라 한다.

Theorem 3.1 : 그래프 G는 odd cycle을 포함하지 않을 때(필요충분조건) bipartite 가 된다. 이는 아래 Lemma 3.2를 이용하여 증명할 수 있다.

Lemma 3.2 : odd 길이의 closed walk(시작 vertex와 끝 vertex가 같은 walk)는 항상 odd cycle을 포함한다.

• tree : cycle이 없고 connected 된 graph

Theorem 3.3 : G가 connected graph 라고 할 때, G의 임의의 두 vertex가 unique path에 의해 join 된다면(필요 충분 조건) , G는 tree이다.

Theorem 3.4 : G가 order가 n이고(v(G) = n) size가 m일때(e(G) = m) m = n-1 이면 G는 tree이다.

--chapter 4--

• k-colouring of G : 그래프 G가 있을때 그래프의 각 vertex를 k 개의 색깔로 칠하는 방법. 단 adjacent(연결된 vertex) 한 vertex끼리는 다른색이여야 한다.
• chromatic number of G : k-colouring of G에서 가장 작은 k 값. X(G) 로 표현.

--chapter 6--

• Euler circuit : connected multigraph 인 G가 있을때 G의 모든 edge를 포함하는 circuit.
• Eulerian multigraph : Euler circuit을 갖는 multigraph, 쉽게 이야기 하면 그래프의 모든 edge를 한번씩 통과해서 시작 vertex로 오게 되는 walk를 갖고 있는 graph

Theorem 6.1 G가 connected multigraph 라고 할 때 G의 모든 vertex의 degree가 even 일때(모든 vertex에 연결된 edge의 갯수가 짝수 일때)만 Euler graph이다.

• spanning cycle : order 가 3이상(vertex의 갯수가 3이상)인 그래프 G가 있을 때 모든 vertex를 통과하는 cycle을 spanning cycle 이라 한다. euler circuit과의 차이는 euler circuit는 모든 edge를 포함해야 한다는 것이며 spanning cycle은 모든 vertex를 포함해야 한다는 것이다.
• hamiltonian graph : spanning cycle을 가지고 있는 graph

Rules for constructing Hamiltonian cycles in G

1. degree가 2인 vertex의 모든 edge는 spanning cycle에 포함되어야 한다.

2. spanning cycle을 만드는 도중에 spanning cycle이 아닌 cycle이 형성될 시에는 그 그래프는 Hamiltonian graph가 될 수 없다.

3. spanning cycle을 만드는 도중에 vertex의 2개의 edge가 정해졌다면 그 vertex에 연결된 그 외의 edge는 제거한다.

Theorem 6.3 G가 만약 Hamiltonian graph 라면 V(G)의 non-empty subset S에 의한 c(G-S)는 |S| 보다 작거나 같다. c(G-S) 는 graph G 에서 subset인 S에 포함되는 vertex와 그 vertex에 연결된 edge를 지운 graph 의 component 갯수를 의미. theorem 6.3은 Hamiltonian graph의 필요 조건.

Theorem 6.4 order가 3 이상인 그래프 G가 있을 때, 모든 vertex에 대해 d(v)가 n/2 이상이 되면 이는 Hamiltonian graph 이다.

Theorem 6.5 order가 3 이상인 그래프 G가 있을때 adjacent vertices를 제외한 모든 vertex 페어에 대해서 d(u) + d(v)가 n 보다 크거나 같으면 이는 Hamiltonian graph 이다.