Mệnh đề P→Q tương đương logic với mệnh đề nào sau đây?

Đỉnh treo (hay còn gọi là lá) là đỉnh có bậc bằng 1. Xét một cây bất kỳ có n đỉnh (n >= 2). Tổng bậc của tất cả các đỉnh trong cây bằng 2(n-1). Nếu mọi đỉnh đều có bậc lớn hơn hoặc bằng 2 thì tổng bậc của tất cả các đỉnh sẽ lớn hơn hoặc bằng 2n. Điều này mâu thuẫn với việc tổng bậc bằng 2(n-1). Vậy nên, trong một cây, luôn tồn tại ít nhất 2 đỉnh có bậc bằng 1, tức là có ít nhất 2 đỉnh treo.

Trong một đồ thị vô hướng G=(V,E) có n đỉnh, ma trận kề là một ma trận vuông kích thước n x n. Phần tử ở hàng i, cột j của ma trận kề biểu diễn cho việc có cạnh nối giữa đỉnh i và đỉnh j hay không. Vì đồ thị là vô hướng, nếu có cạnh nối giữa đỉnh i và đỉnh j thì cũng có cạnh nối giữa đỉnh j và đỉnh i. Do đó, ma trận kề của đồ thị vô hướng đối xứng qua đường chéo chính. Tức là, phần tử ở hàng i, cột j bằng phần tử ở hàng j, cột i.

Phương án A đúng vì ma trận kề của đồ thị vô hướng đối xứng qua đường chéo chính.

Phương án B sai vì ma trận kề phải là ma trận vuông kích thước n x n, không phải 2n.

Phương án C sai vì các giá trị trên đường chéo chính chỉ bằng 1 nếu có cạnh khuyên (loop) tại đỉnh đó. Trong trường hợp tổng quát, giá trị này có thể bằng 0 nếu không có cạnh khuyên.

Phương án D sai vì ma trận kề phải là ma trận vuông kích thước n x n, không phải 2(n – 1).