Course contentsShow
← Computer Science
Lesson 657 of 2,87216. Graphs: Representation and Basic ConceptsFree lesson

What is a Graph? Vertices and Edges

Learn the fundamental definition of a graph as a set of vertices connected by edges, with visual examples.

What is a Graph? Vertices and Edges

You'll learn: The fundamental building blocks of graphs—vertices (nodes) and edges (connections)—and how they form one of the most versatile data structures in computer science.

The Core Idea

A graph is a data structure consisting of two components:

  1. Vertices (also called nodes): Individual points or entities
  2. Edges: Connections or relationships between pairs of vertices

Think of a graph like a social network: each person is a vertex, and each friendship is an edge connecting two people. Or imagine a map where cities are vertices and roads are edges connecting them.

Visual Understanding

In a simple graph with 4 vertices (A, B, C, D):

  • The vertices are the labeled points: A, B, C, D
  • The edges are the lines connecting them: A-B, B-C, C-D, A-D

Unlike trees (which you've studied), graphs have no restrictions on connections. A vertex can connect to many others, connections can form cycles, and there's no concept of a "root" or hierarchy by default.

Key Differences from Trees

While trees are a special type of graph, general graphs are more flexible:

  • Trees have exactly N-1 edges for N nodes; graphs can have any number
  • Trees are always connected; graphs can have isolated vertices
  • Trees have no cycles; graphs often do

Common Graph Terminology

  • Adjacent vertices: Two vertices connected by an edge
  • Degree: The number of edges connected to a vertex
  • Path: A sequence of edges connecting one vertex to another

Key Takeaway: A graph is a collection of vertices (nodes) connected by edges (relationships), forming one of the most general and powerful ways to represent interconnected data.