一個C4與C6飽和二部圖是一個不含有C4與C6的二部圖，且加上任意不相鄰兩點的邊後會形成C4或C6。我們要探討的是一個C4與C6飽和二部圖的邊數為多少。在本論文中，我們令z(m, n)為二部圖Km,n的子圖中為C4與C6飽和圖的最多邊數，s(m, n)為最少邊數。我們獲得以下的結果：
1.s(m ,n)=m+n-1
2.∀n≥3，z(3, n)=n+2、∀n≥4，z(4, n)=n+4，∀n≥6，z(5, n)=n+6
3.若n≥⌊m^2/4⌋，則z(m,n)= ⌊m^2/4⌋+n 
4.設 n≥⌊m^2/4⌋，若s(m ,n)≤ x ≤z(m ,n)，則在 K_(m,n) 中存在一個
C4與C6飽和圖其邊數為x。

A C4, C6-saturated bipartite graph is a bipartite graph if it contains no 4-cycle and 6-cycle, but joining any nonadjacent vertices produces a graph that does contain a 4-cycle or 6-cycle. We will find the number of edges of a C4, C6-saturated bipartite graph. We let z(m, n) be the maximum number of edges of a C4,C6-saturated bipartite graph in Km,n, and s(m, n) be the minimum number of edges of a C4, C6-saturated bipartite graph in Km,n. 
In this thesis, we obtains the following results：

1.s(m,n)=m+n-1
2.∀n ≥ 3, z(3, n) = n+2, ∀n≥4, z(4, n) = n+4, ∀n≥6, z(5, n)= n+6.
3.If n≥⌊m^2/4⌋,then z(m,n)= ⌊m^2/4⌋+n 
4.Let  n≥⌊m^2/4⌋. If s(m,n)≤ x ≤z(m,n), then there exists a subgraph
of K_(m,n) which is a C4, C6-saturated graph, and the number of edges is x.

第一章  簡介	         1
第二章  預備知識	         3
第三章  C4和C6的飽和圖	11
參考文獻	                34

圖目錄
圖1-a、1-b   簡單圖、重邊圖............................ .3 
圖2         3迴圈、4迴圈..............................4
圖3         完全圖K4.................................. 5
圖4         二部圖.................... ................5
圖5         二部圖標法................................ 6
圖6-a,b,c   星圖S4和雙星圖DS(4,4).....................7
圖7         點集圖.................................... 7 
圖8         C4飽和圖...................................8 
圖9         C6飽和圖...................................9
圖10        s(m,n)................................... 11
圖11        二部圖................................... 13
圖12-13     建構z(3,n)的圖........................13-14
圖14-16     建構z(4,n)的圖........................15-16
圖17-22     建構z(5,n)的圖........................16-19
圖23        G和G的點邊圖T(G)....................... 20
圖24        K3,3中具有DS(3,3)的子圖................... 29
圖25~29     K6,9的C4與C6飽和子圖....................30-32

[1]	Bollobes, B., “Extremal Graph Theory,” Academic Press, New York, 1978.
[2]	Culik, K., Teilwesise Losung eines verallgemeinerten Problems von Zarankiewicz, Anna. Soc. Polon. Math. 3 (1956),165-168. 
[3]   Darryn E. Bryant and Hung-Lin Fu. C4-saturated bipartite graphs. Discrete  Math., 259(1-3):263–268, 2002.
[4]	Guy,R.K.,A problem of Zarankiewicz Theory of Graphs, (Rosentstiehl, P. ed.) Gordon and Breach, New York (1967), 139-142.
[5]	Guy, R.K., A problem of Zarankiewicz  Theory of Graphs, (Erdos, P. and Kantona G., eds.) Academic Press, New York (1968), 119-150
[6]	Guy, R.K.,The many faceted problem of Zarankiewicz  The Many Facets of Graphs Theory, Lecture Notes in Maths 110, Springer, (1969), 129-148.
[7]  S. Neuwirth, The size of bipartite graphs with girth eight, arXiv:math.CO/0102210, 2008.

[8]   Z. Furedi, A. Naor, and J. Verstraete, On the Turan number for the hexagon, Adv. Math.203 (2006), 476–496.