• 検索結果がありません。

近畿大学学術情報リポジトリ

N/A
N/A
Protected

Academic year: 2021

シェア "近畿大学学術情報リポジトリ"

Copied!
2
0
0

読み込み中.... (全文を見る)

全文

(1)理工学部研究報告. 31. 第19号. Turanの定理の1つの新しい証明 田. 新. 澤. 成*. A Short Proof of Turan Theorem Shinsei TAZAWA*. The reader is referred to ref.21 for any term not defined below. Let G=(V, E) be a graph having no multiple edges or loops, where V is a vertex-set and E is an edge-set. For two distinct vertices x and y, the edge joining them is denoted by xy. The set of all neighbours of xE:V is denoted by N(x), and d(x)= IN(x) I is called the degree of x. The following theo­ rem due to Tura砂is famous in the field of extremal graph theory: Theorem.. The maximum number of edges among all n vertex graphs with no triangle is. 2. [n /4]. where [r] is the greatest integer not exceeding r. This theorem has been proved in several different methods (for example, see [1 , Chapter 11], [3 , Chapter 2]. ref.41).. In this paper we shall give a new short proof. Suppose that there. exists a graph G=(V, E) with no triangle such that IE/ >[n2/4], where n= /V/. For each edge xyE:E, put S(xy)=(N(x)-{y})U(N(y)-{x}).. Since G does not contain any triangle, it. is clear that N(x)-{y} and N(y)-{x} are disjoint for xyE:E. From this fact we have /S(xy) I �n-2 , which gives工"Y EEIS(xy)/�(n-2)q, where q=/E/. Moreover, 工"YEEIS (xy) !becomes .E ,.EVd(x)(d(x)-1). Thus we have this expression, we get (1). 工d(x) xf:V. エ バvd(x)(d(x)-l)�(n-2)q.. Applying .E ,. EVd(x)= 2q to. に— 2 d(x))琴. The maximum value of the function. エ バvd(x){(n/2)-d(x)} subject to. a constraint. エxf;Vd(x)=. 2q is 2q{(n/2)-(2q/n)}. Since q>[n2/4], it follows that this maximum value is negative, which contradicts (1). Hence if an n vertex graph G=(V, E) does not contain any triangle, then IEl�[n2/4]. Since a graph with n vertices and [n2/4] edges which contains no triangle is a bipartite graph K([n/2], [(n+l)/2]), the proof is completed. References 1) Berge, C., Graphs and hypergraphs, North-Holland, Amsterdam, 1976 . 幻Bollobas, B., Extremal graph theory, Academic Press, London, 1978. 3〕 Haraか瓦Gra抽出的ry, Add誌皿摺因郊監血喝M邸s.. 19⑫ 昭和58年 9 月 10 日受理 *数学物理学科 Department of Physics and Mathematics. - 31 -.

(2) 32. Toran の定理の 1 つの新しい証明. 4〕 如tzkin, T. S. and Straus, E. G., Maxima for graphs and a new proof of a theorem of Turan, Canad. J. Math. 17(1965), 533-540. 的Turan, P., On the theory of graphs, Colloq. Math. 3(1954). 19-30; On a graph theoretical extremal problem, (Hungarian) Mat. Fiz. Lapok 48(1941), 436-452.. - 32-.

(3)

参照

関連したドキュメント

It is also known that every internally triconnected plane graph has a grid drawing of size (n − 1) × (n − 2) in which all inner facial cycles are drawn as convex polygons although

There is also a graph with 7 vertices, 10 edges, minimum degree 2, maximum degree 4 with domination number 3..

We then prove the existence of a long exact sequence involving the cohomology groups of a k-graph and a crossed product graph.. We finish with recalling the twisted k-graph C

We can formulate this as an extremal result in two ways: First, for every graph G, among all bipartite graphs with a given number of edges, it is the graph consisting of disjoint

We note that in the case m = 1, the class K 1,n (D) properly contains the classical Kato class K n (D) introduced in [1] as the natural class of singular functions which replaces the

Given T and G as in Theorem 1.5, the authors of [2] first prepared T and G as follows: T is folded such that it looks like a bi-polar tree, namely, a tree having two vertices

In this paper we describe quantum automorphism groups of vertex-transitive graphs having n ≤ 11 vertices, with one graph omitted.. This enhances previous classification work from

We also recall that a circular space is a complete graph with at least three vertices, viewed as a geometry of rank 2 with vertices and edges as points and lines, respectively.. In