Câu hỏi:

17/06/2026 170

Chứng minh rằng không có đơn đồ thị với 12 đỉnh và 28 cạnh mà các đỉnh đều có bậc 3 hoặc 4.

Trả lời:

verified Giải bởi Vietjack

Lời giải:

Giả sử có đồ thị thỏa mãn yêu cầu bài toán. Gọi x là số đỉnh bậc 3 của đồ thị.

Khi đó, ta có số đỉnh bậc 4 là: 12 – x.

Tổng số bậc của các đỉnh là: 3x + 4(12 – x).

Vì đồ thị có 28 cạnh nên theo Định lí bắt tay thì đồ thị có tổng số bậc là 28 . 2 = 56.

Do đó, ta có phương trình 3x + 4(12 – x) = 56, tức là 8 + x = 0. Phương trình này không có nghiệm là số tự nhiên, do đó không tồn tại đồ thị thỏa mãn điều kiện đề bài.

CÂU HỎI HOT CÙNG CHỦ ĐỀ

Câu 1:

Chứng minh rằng một đồ thị đầy đủ có n đỉnh thì có \(\frac{{n\left( {n - 1} \right)}}{2}\) cạnh.

Xem đáp án » 17/06/2026 291

Câu 2:

Chứng minh đồ thị ở Hình 2.12 là liên thông. Hãy chỉ ra một đường đi nối đỉnh 1 và đỉnh 6.
Media VietJack

Xem đáp án » 17/06/2026 249

Câu 3:

Vẽ hình biểu diễn của đồ thị G với tập đỉnh V(G) = {1; 2; 3; 4; 5} và tập cạnh

E(G) = {12; 14; 23; 25; 34; 35}.

Đồ thị G có phải là đơn đồ thị không? Có phải là đồ thị đầy đủ không?

Xem đáp án » 17/06/2026 246

Câu 4:

Trước khi vào một hồi nghị, các đại biểu bắt tay nhau (hai người bắt tay nhau nhiều nhất 1 lần). Có một đại biểu không bắt tay ai hết và thấy rằng có 4 người bắt tay 4 lần, 5 người bắt tay 5 lần và 6 người bắt tay 6 lần. Nếu hội nghị có đúng 16 đại biểu thì ông ta đếm nhầm. Vì sao có thể kết luận như vậy?

Xem đáp án » 17/06/2026 222

Câu 5:

Cho đồ thị G như Hình 2.14.

a) Tìm một đường đi từ đỉnh A đến đỉnh B.

b) G có liên thông không?

c) Trong G có chu trình sơ cấp nào không?

Media VietJack

Xem đáp án » 17/06/2026 206

Câu 6:

Một đồ thị con của đồ thị G là một đồ thị mà mọi đỉnh của nó đều là đỉnh của G và mọi cạnh của nó cũng là cạnh của G.

Những đồ thị nào trong các hình a), b), c) dưới đây là đồ thị con của đồ thị G?

Media VietJack

Xem đáp án » 17/06/2026 197

Câu 7:

Chứng minh rằng không tồn tại đồ thị với các đỉnh có bậc là 2, 3, 3, 4, 4 và 5. 

Xem đáp án » 17/06/2026 183

Câu 8:

Trong đồ thị ở Hình 2.10, hãy:

a) Tìm một đường đi từ đỉnh A đến đỉnh E.

b) Có tồn tại một đường đi từ đỉnh A đến đỉnh F hay không?

Media VietJack

Xem đáp án » 17/06/2026 176

Câu 9:

Có bốn bạn học sinh khối 11 là An, Bình, Cường và Dung, trong đó: An là bạn của Bình và Cường, nhưng không là bạn của Dung; Dung là bạn của Cường, nhưng không là bạn của Bình; Bình là bạn của Cường.

a) Hãy biểu diễn mỗi bạn An, Bình, Cường, Dung bằng một điểm trên mặt phẳng và dùng chữ cái đầu (in hoa) trong tên của họ để đặt tên cho các điểm này.

b) Nếu hai người là bạn của nhau, hãy nối các điểm biểu diễn tương ứng bằng một đoạn thẳng (hay đoạn đường cong).

c) Từ hình vẽ thu được ở HĐ1b, hãy cho biết: ai có nhiều bạn nhất và ai có ít bạn nhất?

Xem đáp án » 17/06/2026 175

Câu 10:

Vẽ các đồ thị đầy đủ có 5 đỉnh, có 6 đỉnh.

Xem đáp án » 17/06/2026 160

Câu 11:

Cho đồ thị đầy đủ có 5 đỉnh như Hình 2.9. Tìm những chu trình sơ cấp xuất phát từ đỉnh A và có: độ dài 4; độ dài 5.
Media VietJack

Xem đáp án » 17/06/2026 157

Câu 12:

Vẽ đồ thị G với các đỉnh và các cạnh như sau:

V(G) = {U, W, X, Z} và E(G) = {UW, WX, WZ, XZ}.

G có phải là một đơn đồ thị không?

Xem đáp án » 17/06/2026 156

Câu 13:

Cho đồ thị như Hình 2.5. Tìm các đỉnh là đầu mút của: 0 cạnh; 1 cạnh; 2 cạnh; 3 cạnh.
Media VietJack

Xem đáp án » 17/06/2026 147

Câu 14:

Cho đồ thị như Hình 2.7. Bằng cách đi dọc theo các cạnh, với điều kiện không đi qua cạnh nào quá một lần (có thể có cạnh không cần đi qua), hãy chỉ ra các cách để:

a) Đi từ đỉnh A đến đỉnh E.

b) Đi từ đỉnh A và lại quay về đỉnh A.

Media VietJack

Xem đáp án » 17/06/2026 141

Câu 15:

Xét đồ thị nhận được trong Luyện tập 1. Có cặp đỉnh nào của đồ thị này mà không có cạnh nào nối chúng không?

Xem đáp án » 17/06/2026 139

Câu hỏi mới nhất

Xem thêm »
Xem thêm »