Setiap grafik sederhana tanpa arahan dengan lebih dari

Jika grafik dengan simpul memiliki lebih dari tepi maka itu terhubung.$n$$\frac{(n-1)(n-2)}{2}$

Saya agak bingung tentang pertanyaan ini, karena saya selalu dapat membuktikan bahwa untuk menghubungkan grafik, Anda memerlukan lebih dari edge.$|E|>n-1$

Saya tidak yakin apa yang mengganggu Anda, tetapi ketika saya melihatnya Anda bingung tentang dua fakta berikut

1. Jika grafik terhubung maka$e \geq n-1.$

2. Jika grafik memiliki lebih dari maka itu terhubung.$e > \frac{(n-1)(n-2)}{2}$

Perhatikan bahwa implikasi dalam 1 dan 2 berada di arah yang berlawanan.

Untuk bukti 2. Anda dapat melihat tautan ini .

Saya pikir masalah Anda mungkin untuk membuktikan bahwa Anda tidak dapat membuat grafik yang tidak diarahkan dengan tepi yang tidak terhubung. Anda memikirkannya dengan cara yang salah. The rumus tentang bagaimana beberapa tepi yang dapat digunakan untuk menghubungkan semua simpul.$\dfrac{(n-1)(n-2)}{2}$$E = n - 1$

Bayangkan Anda adalah musuh yang mencoba merancang sistem jalan raya yang mengerikan sehingga satu kota terputus. Tidak peduli seberapa efisien Anda menghabiskan jalan Anda, Anda masih harus menghubungkan semua kota jika ada begitu banyak jalan.

Pertimbangkan kemungkinan desain terburuk, misalnya yang menggunakan sebanyak mungkin jalan tetapi masih membuat satu kota terputus. Berapa ujung yang dimiliki? Apa yang terjadi ketika Anda menambahkan satu keunggulan lagi?

1. Seperti yang Anda sebutkan, kami memiliki:

$G\text{ is connected} \Rightarrow |V|-1 \le |E|$

Tetapi arah yang lain tidak benar, yaitu:

$G\text{ is connected} \Leftrightarrow |V|-1 \le |E|$

adalah pernyataan yang salah.

Jadi Anda tidak bisa menggunakannya untuk alasan lebih lanjut. Contoh pencacah contoh adalah grafik ini ( adalah grafik lengkap pada simpul, dan berarti gabungan grafik):$K_t$$t$$\cup$

$G = K_{n-1} \cup K_1$

$G$ memiliki tepi dan simpul, dan untuk .$n-1\choose 2$$n$${n-1\choose 2} > n-1$$n>4$

2. Di sisi lain, untuk membuktikan bahwa:

${|V|-1 \choose 2} < |E| \Rightarrow G\text{ is connected}$

Kita bisa melakukannya sebagai berikut:

Misalkan tidak, maka adalah penyatuan dua grafik yang terpisah , dengan , jika kita menghubungkan semua simpul bersamaan untuk membuat grafik , maka (karena memiliki paling banyak menyelesaikan tepi grafik) tetapi:$G$$G=G_1\cup G_2$$|G_1| = k, |G_2| = n-k, 0<k<n$$G_1,G_2$$G"$$|E_{G"}|\le {n \choose 2}$$G"$

${n-1 \choose 2} + 1 + k\cdot (n-k) \le |E_{G"}| \le {n \choose 2} \Rightarrow$

$(k-1)(n-k-1) + 1 \le 0\Rightarrow$ Bertentangan dengan .$0<k<n$

Grafik G memiliki n simpul n = (n-1) +1 Grafik yang harus diputuskan harus ada setidaknya satu simpul terisolasi. Grafik dengan satu simpul terisolasi memiliki maksimum tepi C (n-1,2).

jadi setiap grafik yang terhubung harus memiliki lebih dari tepi C (n-1,2).