قضیه : میدانیم گرافی k راسی ، اگر بیش از k - 1 یال داشته باشد ، دور دارد ( درخت نیست ، پس دور دارد ) . تعریف : تعداد رؤوس مولفه i ام را ci می نامیم . اثبات : برهان خلف : فرض میکنیم ، نا همیند باشد ، و فرض میکنیم k مولفه داشته باشد( k != 1 ) . چون هیچ مولفه ای دور ندارد ، پس هر مولفه حداکثر ci - 1 یال دارد => در کل حداکثر c1 + c2 + ... + ck -k = n - k یال خواهیم داشت => تناقض ... => یک مولفه ای و همبند است ....

حتی اگه ندونیم درخت چیه هم میشه اثبات کرد که گرافی ک n راس و n-1 یال داره همبنده به این صورت که اول n تا راس ک میخوایم میکشیم بعد با توجه به سوال ک گفته دور نداشته باشه به این صورت عمل میکنیم که راس 1 رو به 2 راس 2 رو به 3 راس 3 رو به 4 . . . تا راس n-1 و n-2 به هم وصل میکنیم ولی راس n-1 رو به راس 1 وصل نمیکنیم چون با توجه به سوال نباید دور داشته باشیم در نتیجه ما الان یک مولفه داریم و n-1 راس ومیتوانیم از هر راس به راسی دیگر برویم در نتیجه گراف ما همبند است .

هم بدون استقرا رو می گم هم استقرا رو: (چون ممکنه بعضی ها بخوان روش استقرا رو بدونن)

بدون استقرا:

طبق تعریف درخت می دانیم:

1) یک گراف درخت است اگر و تنها اگر $n-1$ یال داشته باشد و دور نداشته باشد.

2) و می دانیم که هر درختی همبند است.

بنا به 1 می توانیم بگوییم گراف مورد نظر درخت است و بنا به 2 می توانیم بگوییم که این گراف همبند است.

با استقرا:

حالت پایه: $n=1$ گراف با یک راس همبند است.

اگر برای همه ی گراف های با $n=k$ صحیح باشد.

برای $n=k+1$ به گراف $k$ راسی بدون دور دارای $k-1$ یال یک راس اضافه می کنیم. حال تعداد راس ها $k+1$ است. حال یک یال اضافه می کنیم. اگر این یال بین دو راس از $k$ راس قبلی باشد که تشکیل دور می دهد. پس یال باید بین راس جدید و یکی از راس های قبلی باشد. که در این صورت هم همبند است و هم دور ندارد.