그래프의 응용에 대한 내용은 책 전체를 채울 정도다. 그래프로 표현할 수 있거나 그래프 관점에서 표현하고 풀이하는 문제, 그래프 관련 문제를 풀기 위한 알고리즘은 놀랄 정도로 많다. 이는 현실 세계의 많은 것이 객체와 객체 간의 연결로 구성되어 있기 때문이다. 따라서 현실 세계의 문제를 풀고자 하면 더욱 주목해야 한다.

아마도 그래프를 응용하는 가장 확실한 것은 이미 언급했듯이 네트워크(network)를 표현하는 것이다. 네트워크에서 점은 그래프의 노드이며, 링크는 노드 사이의 간선이다. 서로 다른 많은 네트워크가 있는데, 컴퓨터로 구성된 컴퓨터 네트워크(computer network)는 물론 도로, 항공로, 철길로 연결된 도시 간의 운송 네트워크(transport network)도 있다. 컴퓨터 네트워크로는 인터넷(internet)이 가장 대표적인 예고, 웹(web)은 페이지와 페이지 사이를 하이퍼링크(hyperlink)로 연결한 네트워크다. 위키피디아(wikipedia)는 웹 네트워크의 하위집합으로 규모가 있는 특별한 네트워크이다. 전자 장치 영역에서 회로 기판(circuit board)은 트랜지스터와 같은 전자 부품들이 회로로 연결되어 구성된다. 생물학에서는 물질들 사이의 대사 경로를 포함한 신진대사 네트워크(metabolic network)가 있으며, 화학 물질들이 화학 반응을 통해 연결된다. 소셜 네트워크(social network)는 사람을 노드로, 사람 사이의 관계를 간선으로 하는 그래프로 모델링 된다. 사람 또는 기계 사이에서 일(job)과 과제(task)를 스케줄링(scheduling)하는 것 또한 과제를 노드로, 과제 사이의 선후 종속처리 관계를 간선으로 하여 그래프로 모델링할 수 있다.