Graph Theory Chapter 1 An Introduction to Graphs 大葉大學(Da-Yeh Univ.) 資訊工程系(Dept. CSIE) 黃鈴玲(Lingling Huang)

Outline 1.1 What is a graph? 1.2 The Degree of a Vertex 1.3 Isomorphic Graphs 1.4 Subgraphs 1.5 Degree Sequences 1.6 Connected Graphs 1.7 Cut-Vertices and Bridges 1.8 Special graphs 1.9 Digraphs

Graph Theory 的起源 1736, Euler solved the Königsberg Bridge Problem (七橋問題) Q: 是否存在一 種走法，可以走 過每座橋一次， 並回到起點？ (Ch7 Euler graph)

Königsberg Bridge Problem A B C D  Q: 是否存在一種走法，可以走過每條邊一次，並回到起點？ Ans: 因為每次經過一個點，都需要從一條邊進入該點，再用另一條邊離開，所以經過每個點一次要使用掉一對邊。  每個點上連接的邊數必須是偶數才行  此種走法不存在

An elementary example of graphs 4 students: A, B, C, D 4 positions: FF, SC, W, BS 四人各有喜好的工作：(如下圖，連線表示有興趣) A B C D FF SC W BS Q: Can all four students find jobs they like? (Ch6 Matching) Ans: No

Definition of a graph A graph G is a finite nonempty set V(G) of vertices (also called nodes, 點) and a (possibly empty) set E(G) of 2-element subsets of V(G) called edges (or lines, 邊). V(G) : vertex set of G (只有一個 G 時常簡寫為 V) E(G) : edge set of G (只有一個 G 時常簡寫為 E) 常見的 edge 表示法: {u, v} = {v, u} = uv (or vu) 當邊有方向性時稱 G 為 directed graph (digraph)

Example A graph G=(V,E), where V={u, v, w, x, y, z} E={{u,v}, {u,w}, {w,x}, {x,y}, {x,z}} E={uv, uw, wx, xy, xz} G 的 diagram 表示法: v u w z x y

Adjacent and Incident u, v : vertices of a graph G u and v are adjacent in G if uv  E(G) ( u is adjacent to v, v is adjacent to u) e=uv (e joins u and v) (e is incident with u, e is incident with v) u v e

Graphs types undirected graph: (simple) graph: loop (), multiedge () multiedges, parallel edges undirected graph: (simple) graph: loop (), multiedge () multigraph: loop (), multiedge () Pseudograph: loop (), multiedge ()

order and size The number of vertices in a graph G is called its order (denoted by |V(G)| ). The number of edges is its size (denoted by |E(G)| ). Proposition 1: If |V(G)| = p and |E(G)| = q, then A graph of order p and size q is called a (p, q) graph.

Application of graphs 一群人間兩兩互相認識或不認識(i.e., 沒有A認識B但B不認識A的情形)，在安排一張圓桌的晚餐座位時，是否存在一種排法能讓坐在一起的人都相互認識？ eg. Tom, Dick know Sue, Linda. Harry knows Dick and Linda.  acquaintance graph: (連線表示認識) Tom Dick Sue Linda Harry Q: 圖中是否有一個通過 所有點的cycle? (Ch8 Hamiltonian graph)

Application of graphs eg. Animals: A, B, C, D, E 動物園要用圍牆劃分區域，避免同區的動物互相捕食，至少需分多少區？ eg. Animals: A, B, C, D, E AC 不能與 BD 同區， E不能與其他動物同區 A D E B C 連線表示不能同區 Q: 將圖形的點著色 (一色表示一區)， 若相鄰兩點需塗不同色， 最少需多少顏色才夠？ Ans: 3 色  3 區 (Ch 10 Graph Coloring)

Homework Exercise 1.1: 1, 2, 3, 4

Outline 1.1 What is a graph? 1.2 The Degree of a Vertex 1.3 Isomorphic Graphs 1.4 Subgraphs 1.5 Degree Sequences 1.6 Connected Graphs 1.7 Cut-Vertices and Bridges 1.8 Special graphs 1.9 Digraphs

1.2 The degree of a vertex Definition. For a vertex v of G, its neighborhood N(v) = { u  V(G) | v u  E(G) }. The degree of vertex v is deg(v) = | N(v) |. y u v w x N(u) = {x, w, v}, N(y)={ } deg(u) = 3, deg(y) =0

Notes If |V(G)| = p, then 0  deg(v)  p-1,  v  V(G). If deg(v) = 0, then v is called an isolated vertex (孤立點). v is an odd vertex if deg(v) is odd. v is an even vertex if deg(v) is even.

Handshaking theorem Theorem 1.1 (Handshaking theorem) Let G be a graph, Example 2 3 1 u v w x pf. 在計算degree總和時，每條邊會被計算兩次。

Handshaking theorem Corollary 1.1 Every graph contains an even number of odd vertices. pf. If the number of vertices with odd degree is odd, then the degree sum must be odd. 

Regular graph Definition. A graph G is r-regular if every vertex of G has degree r. A graph G is regular if it’s r-regular for some r. Example Note. There is no 1-regular graph or 3-regular graph of order 5. (by Corollary 1.1) 2-regular

Complement Definition. The complement G of a graph G is a graph with V(G) = V(G), and uv E(G) iff uv  E(G). u v w x G u v w x G

Application of degree Q: n people. (n  2) Is it possible that every two of them are acquainted with a different number of people in the group? (Suppose if A knows B, then B knows A.) A: Consider the acquaintance graph。 若任兩人所認識的人數不等， 表示圖形中所有點的 degree 都不相等。 n 點的圖形中， degree 只可能是 0, 1, …, n-1 (共 n 種)， 必有一點 x 的 degree 為 0，另一點 y 的 degree 為 n-1， 也就是 x 不認識 y ，但 y 認識 x ，矛盾。

Exercise 1 Prove that every graph of order n  2 has at least two vertices with the same degree. (Hint. The problem in previous page.) pf. If not, then there exist vertices x and y with deg(x) = 0 and deg(y) = n-1. It’s impossible.

How many vertices of degree 3 does G have? Exercise 9. Every vertex of a graph G of order 14 and size 25 has degree 3 or 5. How many vertices of degree 3 does G have? sol. Suppose there are x vertices of degree 3, then there are 14-x vertices of degree 5. |E(G)| =25  degree sum=50 3x + 5(14-x) = 50  x = 10

Exercise 10. A graph G of order 7 and size 10 has six vertices of degree a and one of degree b. What is b? Try to draw the graph sol. 6a + b = 20 (a, b) = (0, 20) () (1, 14) () (2, 8) () (3, 2) ()  a=3, b=2.

Homework Exercise 1.2: 4, 7, 11

Outline 1.1 What is a graph? 1.2 The Degree of a Vertex 1.3 Isomorphic Graphs 1.4 Subgraphs 1.5 Degree Sequences 1.6 Connected Graphs 1.7 Cut-Vertices and Bridges 1.8 Special graphs 1.9 Digraphs

1.3 Isomorphic graphs G1 G2 u1 v2 v1 u3 u4 u5 v3 v5 v2 v4 u2 G1 and G2 are the same (after moving some vertices).

Isomorphic Definition. Two graph G1 and G2 are isomorphic (同構) (denoted by G1  G2 ) if there is a 1-1 and onto function  from V(G1) to V(G2) such that uv  E(G1) iff f (u) f (v)  E(G2). (對應過去後，仍能保持兩點間相連與否的關係) The function  is called an isomorphism. In previous page, f (vi) = ui for each i.

Isomorphic Definition. Two graph G1 and G2 are equal if V(G1) = V(G2) and E(G1) = E(G2). Proposition. 1. If G1  G2, then |V(G1)| = |V(G2)| and |E(G1)| = |E(G2)|. 2. If G1  G2 and  is an isomorphism from V(G1) to V(G2), then (So the degree sequences of these graphs must be the same.) 1 跟 2 是判斷兩個圖是否 isomorphic 的初步檢查條件

Definition. Trivial graph: The graph of order 1. Exercise 1 Find two nonisomorphic 3-regular graphs of order 6 and size 9. Sol. G1 G2 contain triangles without any triangle

Exercise 8 Determine whether the graphs G1 and G2 shown below are isomorphic. without any triangle contain triangle Ans: No

2. 要證明 G1  G2 時，只需說明原因 (如：點數 邊數不同，degree sequence不同，或圖形結 構哪裡不同等)。 Note. 1. 要證明 G1  G2 時，必須給出 isomorphism f 這個函數，也就是必須明確說出 G1 的哪一點 對應 G2 的哪一點。 2. 要證明 G1  G2 時，只需說明原因 (如：點數 邊數不同，degree sequence不同，或圖形結 構哪裡不同等)。 所有點的 degree 排列成的數列， 通常由大到小排，1.5節會探討。

Homework Exercise 1.3: 4, 7, 9

Outline 1.1 What is a graph? 1.2 The Degree of a Vertex 1.3 Isomorphic Graphs 1.4 Subgraphs 1.5 Degree Sequences 1.6 Connected Graphs 1.7 Cut-Vertices and Bridges 1.8 Special graphs 1.9 Digraphs

1.4 Subgraphs Definition. A graph H is a subgraph of a graph G if V(H)  V(G) and E(H)  E(G). (denote H  G) Example G u v w x y H v w x y v w x y F  G  G

Induced Subgraph Definition. Let S  V(G), S  . The subgraph induced by S is the maximal subgraph of G with vertex set S. (denoted by <S>) A subgraph H of a graph G is a vertex-induced subgraph if H=<S> for some S  V(G). G u v w x y v w x y H H is not an induced subgraph of G. H ∪{xw}才是

The deletion of vertices Definition. Let S  V(G). The graph G-S = <V(G)-S>. If S={v}, then we write G-v instead. G u v w x y G-S v w Let S={x,u}  u x y

Edge Induced Subgraph Definition. Let X  E(G), X  . The subgraph induced by X is the minimal subgraph of G with edge set X. (denoted by <X>) A subgraph H of a graph G is an edge-induced subgraph if H=<X> for some X  E(G). G u v w x y <X> u v w Let X={uv,vw} 

Exercise 5 If H=<E(G)>, does it follows that H=<V(G)>? Definition. A subgraph H  G is a spanning subgraph of G if V(H) = V(G). Definition. H = G + {uv, uw} means E(H) = E(G) ∪ {uv, uw} , where uv, uwE(G). Exercise 5 If H=<E(G)>, does it follows that H=<V(G)>? G u v w H v w No 

Homework Exercise 6 Let G be a labeled (p, q) graph. How many different edge-induced subgraphs does G have? Note. 不同的邊集合會造出不同的 edge-induced subgraph Ans. 2q-1 ( X  E(G) 且 X , 共有 2q-1 種 X ) Exercise 1.4: 1, 3

Outline 1.1 What is a graph? 1.2 The Degree of a Vertex 1.3 Isomorphic Graphs 1.4 Subgraphs 1.5 Degree Sequences 1.6 Connected Graphs 1.7 Cut-Vertices and Bridges 1.8 Special graphs 1.9 Digraphs

1.5 Degree Sequence Definition. Let G=(V, E), V={v1, v2, …, vp}. Then s: deg(v1), deg(v2), …, deg(vp) is called a degree seqence of G. (For convenient, assume s is nonincreasing, then s is unique.) G 3 2 1 s: 3, 3, 2, 1, 1, 0 maximum degree : D(G) minimum degree : d(G)

Note If d1, d2, …, dp is the degree sequence of some graph, then and 0  d i  p-1 i. For a given sequence s: d1, d2, …, dp of integers such that and 0  d i  p-1 i, there is no guarantee that s is the degree sequence of some graph. ex. s: 5, 5, 3, 2, 1, 0 ( p-1 and 0 can’t exist at the same time) (Moreover, d1 p is impossible. )

Then s is graphical iff s1 is graphical. Definition. We call a sequence of nonnegative integers graphical if it is the degree sequence of some graph. Theorem 1.2 (Havel-Hakimi) Let s be a sequence: d1, d2, …, dp, where di N, i. Let s1 be the sequence: Then s is graphical iff s1 is graphical. (Note. s1 即是把 d1 扣掉，剩下的前 d1 項各減 1。)

Proof of Thm 1.2: (  ) If s1 : is graphical   graph G1 s.t. s1 is the degree sequence of G1 G1 … v2 v3 vd1+1 vd1+2 d2-1 d3-1 vp dd1+1-1 dd1+2 dp d1 vertices  dd1+1 dd1+2 d2 d3 dp G … v2 v3 vd1+1 vd1+2 vp … v1  s : d1, d2, …, dp is graphical.

Proof of Thm 1.2: (continued) (  ) If s : d1, d2, …, dp is graphical   graph G s.t. s is the degree sequence of G with deg(vi) = di for 1  i  p, and is maximum. Claim: { v1v2, v1v3, …, v1vd1+1}  E(G) v1 G … v2 v3 vd1+1 vd1+2 d2 d3 vp dd1+1 dd1+2 dp d1 i.e., : : If the claim is true, then G-v1 is a graph with degree sequence s1  s1 is graphical.

Claim: { v1v2, v1v3, …, v1vd1+1}  E(G) Proof: If not, there must be two vertices vj and vk (j < k) with dj > dk s.t. v1vk  E(G) but v1vj  E(G). v1 G vj vk vn Since dj > dk,  vnV(G) s.t. vjvn  E(G), vkvn  E(G). Let G2 = G - {v1vk, vjvn} + {v1vj, vkvn} G2 has degree seq s but larger , 

Algorithm s: d1, d2, …, dp sequence of integers To determine whether s is graphical: (1) If di=0, i, then s is graphical. If  di<0 for some i, then s is not graphical. Otherwise, go to (2). (2) Reorder s to a nonincreasing sequence if necessary. (3) Let s = s1, (s1的產生方式同 Thm 1.2), return to (1).

Example 1 s: 4, 4, 3, 3, 2, 2 s1’: 3, 2, 2, 1, 2 (delete the first 4) s1: 3, 2, 2, 2, 1 (reorder) s2: 1, 1, 1, 1 (delete 3) s3’: 0, 1, 1 (delete the first 1) s3: 1, 1, 0 (reorder) s4: 0, 0 (delete the first 1)  s is graphical

Draw the graph s: 4, 4, 3, 3, 2, 2 s1’: 3, 2, 2, 1, 2 s1: 3, 2, 2, 2, 1 s2: 1, 1, 1, 1 s3’: 0, 1, 1 s3: 1, 1, 0 s4: 0, 0  s is graphical G 4 2 3

Example 2 s: 5, 4, 3, 2, 1, 1 s1: 3, 2, 1, 0, 0 (delete 5) s2: 1, 0, -1, 0 (delete 3)  s is not graphical

Definition. Let G=(V,E), the set D (G)={deg(v) | vV } is called the degree set of G. Ex. s: 4, 4, 3, 3, 2, 2 D (G)={ 2, 3, 4 } (去掉順序及重複性) Kapoor et al [7] showed that Every finite set of nonnegative integers is the degree set of some graph.

Let |V(G)|=12, D (G){4, 5, 6}. Show that G contains either Exercise 6 Let |V(G)|=12, D (G){4, 5, 6}. Show that G contains either (i) at least 4 vertices of degree 4, (ii) at least 6 vertices of degree 5, (iii) at least 5 vertices of degree 6. Proof If not, deg 4 點數  3 deg 5 點數  5 deg 6 點數  4 deg 4 點數 = 3 deg 5 點數 = 5 deg 6 點數 = 4 3+5+4=12   degree總和不為偶數 

Exercise 8 Let G be a graph with D (G) = {m, n}, where G contains m vertices of degree m and n vertices of degree n. Prove that if G contains an odd vertex, then every vertex of G is odd. Proof degree sum = m2 + n2 If m is odd then n must be odd, and vice versa.

Homework Exercise 1.5: 1, 3, 5, 7, 9

Outline 1.1 What is a graph? 1.2 The Degree of a Vertex 1.3 Isomorphic Graphs 1.4 Subgraphs 1.5 Degree Sequences 1.6 Connected Graphs 1.7 Cut-Vertices and Bridges 1.8 Special graphs 1.9 Digraphs

1.6 Connected graphs Definition. A walk in a graph G is an alternating sequence W: v0, e1, v1, e2, v2, …, vn-1, en, vn (n0) of vertices and edges, where ei=vi-1vi, i. ( 故 W 中的 ei 可省略) (W is also called a v0 -vn walk) W is said to have length n. A trail is a walk without repeated edges. A path is a walk without repeated vertices. G u v w x y walk: x, w, v, x, w trail: x, w, v, x, y path: x, w, v

Theorem 1.3 Every u-v walk in a graph contains a u-v path. Proof. 去掉重複的點或邊即可 Definition (1) A cycle is a walk v0, v1, v2, …, vn-1, vn in which n3, v0 = vn, and v1, v2, …, vn-1, vn are distinct. (n-cycle) (2) A u-v walk is closed if u=v. (closed walk) (3) A nontrivial closed trail is called a circuit.

Definition (1) Let u,vV(G), u is connected to v if  u-v path. (2) G is connected if u is connected to v u,v  V(G), otherwise, G is called disconnected. (3) A subgraph H of G is a component of G if H is a maximal connected subgraph of G. (4) The number of components of G is denoted by k (G). Note. “is connected to” is an equivalence relation

Exercise 7 Let G be a graph. |V(G)|=p, p2. Suppose d(G)  (p-1)/2. Prove that G is connected. Proof If G is disconnected, since d(G)  (p-1)/2, each component must contain (p+1)/2 vertices. 

(1) 若點沒有重複此walk本身即odd cycle (2) 若點 x 重複出現 Exercise 10 Prove that if a graph G has a closed walk of odd length, then it has a cycle of odd length. Proof. (1) 若點沒有重複此walk本身即odd cycle (2) 若點 x 重複出現 設此walk P: v0=x, v1, v2, …, vi=x, vi+1, …, vn, v0=x 其中 vi 是從v0走到vn的過程中， x 最後一次出現 則可將P分成兩個closed walk: P1: v0=x, v1, v2, …, vi=x P2: vi=x, vi+1, …, vn, v0=x 兩者必有一為odd length 取此一walk仿照上述方法再拆，最後必可得一odd cycle.

Exercise 11 Show that a graph G contains (1) a path of length d(G), and (2) a cycle of length at least d(G) +1 if d(G)  2. Proof: Let P: v0, v1, …, vk be a longest path of G. Then deg(v0)  d(G), and N(v0 )  V(P) for otherwise P is not longest. It follows that the length of P is at least d(G). Let vn be the vertex of P with v0vn E(G) and n is largest. If d(G)  2, then n  2. Let C: v0, v1, …, vn, v0. Since N(v0)  V(C), It is clear that the length of C is at least d(G) +1.

Homework Exercise 1.6: 1, 2, 3, 4, 5, 8, 9

Outline 1.1 What is a graph? 1.2 The Degree of a Vertex 1.3 Isomorphic Graphs 1.4 Subgraphs 1.5 Degree Sequences 1.6 Connected Graphs 1.7 Cut-Vertices and Bridges 1.8 Special graphs 1.9 Digraphs

1.7 Cut Vertices and Bridges Definition 1 A vertex v in a graph G is called a cut-vertex if k(G - v) > k(G). So v is a cut-vertex in a connected graph G if G - v is disconnected.

e.g. G : cut-vertex： 　　　　　　　　　　　　 v3, v5 cut-edge： v5v6 v1 v2 v3 v5 v4 v6

Definition 2 An edge e in a graph G is called a bridge (cut-edge) if k(G - e) > k(G). e.g. The graph in previous page: v5v6 is a bridge. Note. (1) if v is a cut-vertex of a connected graph G, then k(G - v)  2 (2)If e is a bridge of a connected graph G, then k(G - e) =2

Claim: G - e is connected. Theorem 1.4 An edge e of a connected graph G is a bridge iff e does not lie on a cycle of G. Proof. () Let e be a bridge of G. Suppose e =uv, and assume, to the contrary, that e lies on a cycle C：u, v, w, …, x, u. 　Then C - e：v, w, …, x, u is a u-v path of G - e. Claim: G - e is connected. (If the claim is true, ) (e is not a bridge)

 (Proof of above Claim) Let u1, v1  V(G-e)=V(G) ∵G is connected ∴ u1-v1 path P in G. If e  P, then P is also a path in G-e   u1-v1 path in G-e If e  P, then (PC)-e is a u1-v1 walk in G-e ∴  u1-v1 path in G-e Therefore, G-e is connected. v1  u u1 v C P

() Suppose e=uv is an edge that lies on no cycle of G () Suppose e=uv is an edge that lies on no cycle of G. Then G-e contains no u-v path. Otherwise, if P is a u-v path in G-e, then P { uv } is a cycle containing e,  .

Definition 3 A nontrivial connected graph without a cut-vertex is called a nonseparable graph. A block B of a nontrivial connected graph G is a subgraph of G that itself is a maximal nonseparable graph. # of vertices 2

e.g. G G has 3 blocks： <{v1,v2,v3}>, <{v3,v4,v5}>, <{v5,v6}> v1 v2 v3 v4 v5 v6

Note: 1. A block is necessarily an induced subgraph. 2. The blocks of a graph produce a partition of the edge set of the graph. 3. Every two blocks have at most one vertex in common. 4. If v V(B1)V(B2), where B1, B2 are block of G, then v is a cut-vertex. 5. If G is nonseparable, then G is a block.

Definition A block of a graph G that contains exactly one cut-vertex of G is called an end-block of G. Theorem 1.5 Let G be a connected graph with at least one cut-vertex. Then G has at least two end-blocks. (介紹到tree時再証)

Homework Exercise 1.7: 1, 2, 4, 5, 6, 7

(b) Is the statement in (a) still true if r is odd? HW3 (a) Show that if G is an r-regular connected graph, where r is even, then G contains no bridges. (b) Is the statement in (a) still true if r is odd? Sol： (a) If G has a bridge e, assume G = G1G2 {e}, where e=ab, G1 and G2 are the two components of G-e. G1 G2 a b

Consider the subgraph G1 v V(G1), degG (v)= r if v a r-1 if v=a ∵r is even ∴ is odd  1

(b) No, e.g. r = 1 G： r = 3

HW4 Find a counterexample (a) If G is a connected graph that contains only even vertices, then G contains no cut-vertices. Sol.

HW8 A connected graph G contains three distinct vertices u, v and w with the property that every u-w path in G contains v. Show that v is a cut-vertex. Proof. Consider G-v, there is no u-w path in G-v.  k(G-v)>1 = k(G)  v is a cut-vertex.

Outline 1.1 What is a graph? 1.2 The Degree of a Vertex 1.3 Isomorphic Graphs 1.4 Subgraphs 1.5 Degree Sequences 1.6 Connected Graphs 1.7 Cut-Vertices and Bridges 1.8 Special graphs 1.9 Digraphs

1.8 Special Graphs Def 1. Complete graph (Kp) : p vertices, p 1 , u~v, u,v  V (Kp) Note. (1) Kp is (p-1) regular (2) Kp has edges. K5

A path of order n (denoted by Pn) : a path of n vertices. (length n-1) Def 2. A path of order n (denoted by Pn) : a path of n vertices. (length n-1) Def 3. n-cycle (denoted by Cn) : a cycle of n vertices, n  3. even cycle : a cycle of even vertices odd cycle : a cycle of odd vertices P4 C5

∪ Def 4. A graph G is bipartite if V(G)=V1 V2 disjoint union Def 4. A graph G is bipartite if V(G)=V1 V2 s. t. every edge of G joins a vertex of V1 and a vertex of V2. ( (V1, V2) is called a bipartition of G. ) + ∪ e.g. redrawn of G G: V1 V2 v1 v2 v4 v3 v6 v5 v1 v6 v4 v5 v3 v2

If  u-v path in G, d(u, v) = ∞. e.g. 上圖 G 中 d(v1, v4) = 1 Def 5. (先補充) If  u-v path in G , the distance between u and v, denoted by d(u, v), is the length of shortest u-v path. If  u-v path in G, d(u, v) = ∞. e.g. 上圖 G 中 d(v1, v4) = 1 d(v1, v6) = 2 d(v4, v6) = 3 v1 v2 v4 v3 v6 v5

Thm 1.6 A nontrivial graph G is bipartite iff G has no odd cycles. Pf: ) Assume G is a bipartite graph with bipartition (V1,V2). If Cn : v1,v2,…,vn,v1 is any cycle of G. (n3) Suppose v1V1, then v2V2, v3V1, v4V2, …, vnV2 Hence n must be even, G has no odd cycles.

) It clearly suffices to prove the converse of connect graphs. Let G be a connected graph without odd cycles. Choose any vertex uV(G), define V1 = { wV(G) | d(u, w) is even} V2 = { wV(G) | d(u, w) is odd} (Show that (V1, V2) is a bipartition of G).

Choose any two vertices v,wV1 (or v,wV2 ). Let P be a shortest u-v path and Q be a shortest u-w path. (P,Q may have several common vertices.) Let u1 be the last vertex common to P and Q. Let P’ be the subpath of P connecting u1 and v, Q’ be the subpath of Q connecting u1 and w. length(P-P’) = length(Q-Q’)  d(u1,v)+d(u1,w) is even. If vwE(G), then P’∪Q’∪{vw} is a cycle of odd length.  v u u1 w P ∴ vwE(G), v,wV1 or v,wV2  G is bipartite. Q

Def 6. Complete bipartite graph Km,n : V(Km,n) = V1∪V2 , where |V1|=m , |V2|=n. uV1 and vV2 , uvE(Km,n). Note : |V(Km,n)| = m+n |E(Km,n)| = mn. K3,2

The graph K1,n (or Kn,1) is called a star. Def 7. The graph K1,n (or Kn,1) is called a star. e.g. K1,1  K2 K1,2  P3 K2,2  C4

Def 7. (n-partite graph) (n2) A graph G is an n-partite graph if V(G) can be partitioned into n nonempty subsets V1,V2,…,Vn such that no edge of G joins vertices in the same set. (V1,V2,…,Vn are called the partite sets of G) 3-partite graph V1 V3 V2

e.g. Def 8. Complete n-partite graph Kp1,p2,…,pn : V(Kp1,p2,…,pn) = V1∪ V2∪…∪Vn where |Vi|=Pi , i E(Kp1,p2,…,pn) = {uv | uVi , vVj with i≠j } + + + e.g. K1,1,1,1  K4

K1,2,2  v1 v4 v6 v5 v2 v3 K2,2,2 

Def 9. Let G1,G2 be vertex-disjoint graphs. The union of G1,G2 is the graph G1∪G2 having V(G1∪G2) = V(G1)∪V(G2) E(G1∪G2) = E(G1)∪E(G2) If G1  G2  G then we write 2G for G1∪G2.

(2) The join of G1, G2 is the graph G1+G2 having V(G1+G2) = V(G1)∪V(G2) E(G1+G2) = E(G1)∪E(G2)∪{v1v2 : v1V(G1), v2V(G2)} e.g. P3 : K2 : P3+K2 :

(3) For graphs G1 and G2, the product G1 × G2 has vertex set V(G1×G2)= V(G1) × V(G2) ={ (u1, u2) : u1V(G1) , u2V(G2)} and (u1, u2) ~ (v1, v2) iff u1 = v1 and u2 v2  E(G2) or u2= v2 and u1 v1  E(G1)

e.g. 直覺的想法： G1G2可視為在G1 中每個點的位置放一個G2 及在G2 中每個點的位置放一個G1 K3P3： a1 K3： (a1, b1) (a2, b1) (a3, b1) a2 a3 (a1,b2) (a2, b2) (a3, b2) b1 (a1,b3) (a2, b3) (a3, b3) P3： b2 b3 直覺的想法： G1G2可視為在G1 中每個點的位置放一個G2 及在G2 中每個點的位置放一個G1

Definition 10. 在考慮product時, 有一類圖形常被提到： The hypercube or n-cube Qn is defined as Q1= K2 Qn= Qn-1K2 if n  2 　 Q2： Q1： (0,0) (0,1) (1,1) (1,0) 1

V(Qn) can be written as {(a1, a2, …, an) | ai=0 or 1} (0,0,1) (0,1,1) (1,1,1) (1,1,0) (0,1,0) (1,0,0) (0,0,0) (1,0,1) Note. V(Qn) can be written as {(a1, a2, …, an) | ai=0 or 1}

Homework Exercise 1.8: all, except 10(b)(c) , 11

HW4 Let G be a graph. The subdivision graph S(G) of G is the graph obtained by replacing each edge e=uv of G by a new vertex ve, and joining ve to u and v. 每條邊上多加一點 u v c b a e.g. a b c v u

HW4 (continued) Show that if G is any nontrivial graph, then S(G) is bipartite. Proof. Let V(S(G)) = V(G)  D, where D={ve：eE(G)} Then u, vV(G), u ~ v in S(G) and w, xD, w ~ x in S(G) So (V(G), D) is a bipartition of S(G). # \ \

(Method 1) If not, G has an odd cycle  HW9 Let G be a graph with the property that every edge joins an even vertex and an odd vertex. Prove that G is bipartite. Proof. (Method 1) If not, G has an odd cycle  odd even contradiction

where V1 = {all even vertices} V2 = {all odd vertices} (method 2) Let V(G)=V1 V2, where V1 = {all even vertices} V2 = {all odd vertices} then (V1, V2) is a bipartition of G. +

Outline 1.1 What is a graph? 1.2 The Degree of a Vertex 1.3 Isomorphic Graphs 1.4 Subgraphs 1.5 Degree Sequences 1.6 Connected Graphs 1.7 Cut-Vertices and Bridges 1.8 Special graphs 1.9 Digraphs

1.9 Digraphs Definition 1: A digraph (or directed graph) D is a finite, nonempty set V(D) of vertices and a set E(D) of ordered pairs of distinct vertices . The elements of E(D) are called arcs . e.g. v u x w D : E(D) ={(v,u),(u,w), (v,w),(x,w),(w,x)}

The underlying graph of a diagraph D: Definition 2: The underlying graph of a diagraph D: 去掉邊的方向性後得到的simple graph. (Note: becomes ) x w x w Definition 3: u is adjacent to v v is adjacent from u (u,v) is incident from u and incident to v. u v

Definition 4: outdegree of v : od v (textbook) , deg+(v) v indegree of v : id v, deg -(v) v Thm 1.7: Let D be a digraph, then Thm 1.7: Let D be a digraph, then ※ Many properties are similar with simple graphs, but the length of a cycle can be 2.

semiwalk : 不管邊之方向性的walk Definition 5: semiwalk : 不管邊之方向性的walk e1 e2 e3 e4 W: … v0 v1 v2 v3 v4 vn (ei = (vi-1,vi) or (vi,vi-1) ) Definition 6: Two vertices u and v in a digraph D are connected if D contains a u-v semiwalk.

Definition 7: ① A diagraph D is connected if every two vertices of D are connected. (also called weakly connected) ② A diagraph is (單方向的) unilaterally connected if for every two distinct vertices u and v there is a u-v path or a v-u path. ③ A diagraph is strongly connected if for every two distinct vertices u and v there is a u-v path and a v-u path. Definition 8: G is symmetric if  G is asymmetric if    u v v u u v   v u

multidigraph : allowed pseudodigraph: allowed v Definition 9: multidigraph : allowed pseudodigraph: allowed u v and Definition 10: A digraph D in which either is called a tournament. u v or  u,v V(D) (not both)

Homework HW3: Exercise 1.9: 3, 8, 10, 11 Show that a strong (strongly connected) digraph of order p  2 contains a cycle of length n for some n  2 .