그래프 이론에서 연결 그래프(連結graph, 영어: connected graph)는 모든 두 꼭짓점 사이에 경로가 존재하는 그래프이다.

그래프 ${\displaystyle G}$의 서로 다른 두 꼭짓점 ${\displaystyle u,v\in V(G)}$에 대하여, ${\displaystyle u}$와 ${\displaystyle v}$ 사이의 경로가 존재한다면 두 꼭짓점이 연결되었다(영어: connected)고 한다.

연결 그래프(영어: connected graph)는 임의의 서로 다른 두 꼭짓점이 연결된 그래프이다. 그래프의 연결 성분(영어: connected component)은 (포함 관계에 대한) 극대 연결 부분 그래프이다.

그래프 ${\displaystyle G}$ 및 그 꼭짓점의 집합 ${\displaystyle S\subset V(G)}$에 대하여, 꼭짓점을 제거한 그래프 ${\displaystyle G\setminus S}$를 다음과 같이 정의하자.

• ${\displaystyle V(G\setminus S)=V(G)\setminus S}$
• ${\displaystyle uv\in E(G\setminus S)\iff uv\in E(G)\quad \forall u,v\in V(G\setminus S)}$

만약 ${\displaystyle G\setminus S}$가 비연결 그래프이거나 자명 그래프 ${\displaystyle K_{1}}$인 경우, ${\displaystyle S}$를 ${\displaystyle G}$의 꼭짓점 절단(영어: vertex cut)이라고 한다. 꼭짓점 절단들은 포함 관계에 따라서 부분 순서 집합을 이루며, 그 극소 원소를 극소 꼭짓점 절단(영어: minimal vertex cut)이라고 한다. 절단 가운데 크기가 가장 작은 것을 최소 꼭짓점 절단(영어: minimum vertex cut)이라고 한다. 그래프 ${\displaystyle G}$의 꼭짓점 연결성(영어: vertex connectivity) ${\displaystyle \kappa (G)}$은 그 최소 꼭짓점 절단의 크기다.

그래프 ${\displaystyle G}$ 및 기수 ${\displaystyle k}$에 대하여, 만약 ${\displaystyle k\leq \kappa (G)}$라면 ${\displaystyle G}$를 ${\displaystyle k}$-꼭짓점 연결 그래프(영어: ${\displaystyle k}$-vertex-connected graph)라고 한다. 연결 그래프는 1-꼭짓점 연결 그래프와 같다.

그래프 ${\displaystyle G}$ 및 그 변의 집합 ${\displaystyle T\subset E(G)}$에 대하여, 변을 제거한 그래프 ${\displaystyle G\setminus T}$를 다음과 같이 정의하자.

• ${\displaystyle V(G\setminus T)=V(G)}$
• ${\displaystyle uv\in E(G\setminus T)\iff uv\in E(G)\setminus T\quad \forall u,v\in V(G\setminus T)}$

만약 ${\displaystyle G\setminus T}$가 비연결 그래프인 경우, ${\displaystyle T}$를 ${\displaystyle G}$의 변 절단(영어: edge cut)이라고 한다. 변 절단들은 포함 관계에 따라서 부분 순서 집합을 이루며, 그 극소 원소를 극소 변 절단(영어: minimal edge cut)이라고 한다. 절단 가운데 크기가 가장 작은 것을 최소 변 절단(영어: minimum edge cut)이라고 한다. 그래프 ${\displaystyle G}$의 변 연결성(영어: edge connectivity) ${\displaystyle \lambda (G)}$은 그 최소 변 절단의 크기다. 크기가 1인 최소 변 절단을 다리(영어: bridge)라고 한다.

그래프 ${\displaystyle G}$ 및 기수 ${\displaystyle k}$에 대하여, 만약 ${\displaystyle k\leq \lambda (G)}$라면 ${\displaystyle G}$를 ${\displaystyle k}$-변 연결 그래프(영어: ${\displaystyle k}$-edge-connected graph)라고 한다.

그래프 ${\displaystyle G}$가 연결 그래프라고 하자. 그렇다면, 다음 그래프들 역시 연결 그래프이다.

• ${\displaystyle G}$의 그래프 준동형사상에 대한 상 ${\displaystyle \phi (G)}$
• ${\displaystyle G}$의 선 그래프 ${\displaystyle L(G)}$

그래프 ${\displaystyle G}$에 대하여, 다음이 성립한다.

${\displaystyle \kappa (G)\leq \lambda (G)\leq \min _{v\in V(G)}\deg v}$

차수가 ${\displaystyle d\geq 2}$인 꼭짓점 추이적 그래프(영어: vertex-transitive graph) ${\displaystyle G}$에 대하여, 다음이 성립한다.^[1]

${\displaystyle \lceil 2(d+1)/3\rceil \leq \kappa (G)\leq \lambda (G)=d}$

특히, ${\displaystyle d=2,3,4}$인 경우 ${\displaystyle \kappa (G)=\lambda (G)=d}$이다.

간단한 그래프의 꼭짓점·변 연결성은 다음과 같다.

그래프	꼭짓점 연결성	변 연결성
비연결 그래프	0	0
완전 그래프 ${\displaystyle K_{n}}$ (${\displaystyle n\geq 1}$)	${\displaystyle n-1}$	${\displaystyle n-1}$
나무 (꼭짓점 2개 이상)	1	1
순환 그래프 ${\displaystyle C_{n}}$ (${\displaystyle n\geq 3}$)	2	2
라도 그래프	${\displaystyle \aleph _{0}}$	${\displaystyle \aleph _{0}}$

• Diestel, Reinhard (2010). 《Graph theory》. Graduate Texts in Mathematics (영어) 173 4판. ISBN 978-3-642-14278-9. Zbl 1204.05001.  CS1 관리 - 추가 문구 (링크)

• “Graph, connectivity of a”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• Weisstein, Eric Wolfgang. “Connected graph”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Disconnected graph”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Biconnected graph”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “k-connected graph”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Edge connectivity”. 《Wolfram MathWorld》 (영어). Wolfram Research.