連通無向圖結論

因此連通無向圖定義可推。同理，非連通無向圖亦可推。

任意一條邊都代表u連v以及v連u。無向圖是相對于有向圖來說明的，就是說每條邊都是雙向邊，而有向圖每條邊都是單向邊，也就是說只能由一個點指向另一個點。

即是任何兩個點都有路徑相連。

在圖論中，連通圖基于連通的概念。在一個無向圖 G 中，若從頂點vi到頂點vj有路徑相連(當然從vj到vi也一定有路徑)，則稱vi和vj是連通的。如果 G 是有向圖，那么連接vi和vj的路徑中所有的邊都必須同向。如果圖中任意兩點都是連通的，那么圖被稱作連通圖。如果此圖是有向圖，則稱為強連通圖(注意:需要雙向都有路徑)。圖的連通性是圖的基本性質。

一個無向圖 G=(V,E) 是連通的，那么邊的數(shù)目大于等于頂點的數(shù)目減一:|E|>=|V|-1，而反之不成立。

如果 G=(V,E) 是有向圖，那么它是強連通圖的必要條件是邊的數(shù)目大于等于頂點的數(shù)目:|E|>=|V|，而反之不成立。

沒有回路的無向圖是連通的當且僅當它是樹，即等價于:|E|=|V|-1。

連通分量:無向圖 G的一個極大連通子圖稱為 G的一個連通分量(或連通分支)。連通圖只有一個連通分量，即其自身;非連通的無向圖有多個連通分量。

強連通圖:有向圖 G=(V,E) 中，若對于V中任意兩個不同的頂點 x和 y，都存在從x到 y以及從 y到 x的路徑，則稱 G是強連通圖。相應地有強連通分量的概念。強連通圖只有一個強連通分量，即是其自身;非強連通的有向圖有多個強連分量。

單向連通圖:設G=<V,E>是有向圖，如果u->v意味著圖G至多包含一條從u到v的簡單路徑，則圖G為單連通圖。

弱連通圖:將有向圖的所有的有向邊替換為無向邊，所得到的圖稱為原圖的基圖。如果一個有向圖的基圖是連通圖，則有向圖是弱連通圖。

初級通路:通路中所有的頂點互不相同。初級通路必為簡單通路，但反之不真。