※ [本文轉錄自 NTU-Exam 看板]
作者: abcde1234 (沌魂) 看板: NTU-Exam
標題: [試題] 94下 張鎮華 圖論二 期中考
時間: Sun Jun 25 20:48:45 2006
課程名稱︰圖論二
課程性質︰U選修
課程教師︰張鎮華
開課系所︰數學系、數學所
考試時間︰4/13 56節
是否需發放獎勵金：是
試題 :
Extamination1 (Graph therory,second semester)
Each problem weights 20 points. 2006-4-13(Gerard J. Chang)
1.(a) Prove that if a connected plane graph G has exactly n vertices, e edges
, and f faces, then n-e+f=2.
(b) Prove that K_5 and K_3,3 are not planar.
(c) Suppose S is a set of n>=3 points in the plane such that for any pair
of distinct points x,y in S, the distance between x and y in the plane
is at least 1. Prove that there are most 3n-6 pairs u,v in S such that
the distance between u and v in the plane is exactly 1.
(d) Can the upper bound 3n-6 in (c) be reduced?
2.(a) Prove that every minimal non-planar graph is 2-connected.
(b) Prove that if G is a graph with fewest edges among all non-planar
graphs with no subdivision of K_5 or K_3,3, then G is 3-connected.
(c) Prove that is G is a 3-connected graph with no subdivision of K_5 or
K_3,3, then G has a convex embedding in the plane with no three
vertices on a line. You may use the folowing two lemmas.
Lemma A: Every 3-connected graph G with at least five vertices has an edge
e such that G．e is 3-connected.
Lemma B: If G has no subdivision of K_5 or K_3,3 , the so is G．e.
3.Recall that ν(G) is the crossing number of graph G.
(a) Show that ν(K_3,2,2)=2 and ν(K_3,3,1)=3.
(b) Show that 5<=ν(K_3,3,2)<=7 and 9<=ν(K_3,3,3)<=15.
(c) Show that ν(K_n,n,n) >=n^3(n-1)/6.
(d) Show that ν(K_n,n,n) <=(9/16)n^4 + O(n^3).
4.(a) Prove that if G is a simple graph then χ'(G)<=△+1.
(b) Use (a) to prove that every simple graph with maximum degree △ has an
"equitable" (△+1)-edge-coloring, which is a proper edge-coloring with
each color used ┌e(G)/(△+1)┐ or [e(G)/(△+1)] times.
^^^^^^^^^^^^^^ ^^^^^^^^^^^^^ 是指上高斯和下高斯
5. Prove that if κ(G)>=α(G), then G has a Hamiltonian cycle (unless G=K_2).