What is a Graph?

A graph is a way to represent relationships between objects. In mathematics and computer science, a graph consists of:

• Vertices (nodes) → the objects
• Edges (links/connections) → the relationships between the objects

For example, in a social network:

• People = nodes
• Friend connections = edges

Main Types of Graphs

There are many types of graphs in Graph Theory. Here, we mention 13 major graph types.

1. Undirected Graph

Edges have no direction. This means that if node A is connected to node B, then node B is also connected to node A.

Example:

Friend networks: friendship is usually a two-way relationship. If A is a friend of B, then B is also a friend of A.

2. Directed Graph (Digraph)

Edges have a direction. This means the connection goes from node A to node B only.

Example:

Instagram follows: if A follows B, it does not necessarily mean that B follows A.

 

3. Weighted Graph

Edges contain a weight or value, such as distance, cost, or time.

Example:

GPS navigation systems use weighted graphs where roads may have weights representing distance or traffic conditions.

4. Unweighted Graph

Edges do not contain weights or values.

Example:

Simple relationship mapping where only the existence of a connection matters.

5. Connected Graph

A graph is connected if every node can be reached from every other node.

A graph is disconnected if some nodes cannot be reached from others.

7. Cyclic Graph

A cyclic graph contains at least one cycle (closed loop).

An acyclic graph contains no cycles.

Uses

• Task scheduling
• Dependency systems

9. Complete Graph

In a complete graph, every node is connected to every other node.

Example (4 nodes):

• A connected to B, C, and D
• B connected to C and D
• C connected to D

10. Simple Graph

A simple graph follows two rules:

1. No self-loops
   A node cannot connect to itself.
2. No multiple edges
   There can be only one edge between any two nodes.

11. Multigraph

A multigraph is a graph in which multiple edges are allowed between the same pair of nodes.

Unlike a simple graph, a multigraph may contain:

• Two or more edges connecting the same nodes
• Self-loops (depending on the definition)

12. Bipartite Graph

In a bipartite graph, nodes are divided into two groups, and edges connect only nodes from different groups.

Uses

• Job assignment systems
• Recommendation systems

13. Tree

A tree is a special type of graph that:

• Is connected
• Has no cycles

Uses

• File systems
• Organization charts

Broad Classification of Graphs

 

Graph Theory in LangGraph

Designing a graph is one of the first steps in building an AI agent. Therefore, understanding graph concepts helps developers create well-designed and efficient agents. The most important graph concepts in LangGraph are shown below. 

• Directed Graph 
• Cyclic Graph 
• DAG (Directed Acyclic Graph) 
• Tree Structures 
• Self-loop Workflows (special cyclic case)

Example Mapping

 

The table below demonstrates each graph type, its feasibility, and how it appears in LangGraph.

Graph Type	Can Be Implemented in LangGraph?	How It Appears in LangGraph
Undirected Graph	No (not typical)	LangGraph workflows have execution direction, so edges are directed
Directed Graph	Yes	Core structure of LangGraph workflows
Weighted Graph	Partially	Weights are not built-in graph properties, but priorities/costs can be simulated in logic
Unweighted Graph	Yes	Most LangGraph workflows are effectively unweighted
Connected Graph	Yes	Typical workflows connect all reachable nodes
Disconnected Graph	Yes	Possible technically, but usually avoided because unreachable nodes are useless
Cyclic Graph	Yes	One of LangGraph’s key strengths; supports loops and agent cycles
Acyclic Graph (DAG)	Yes	Simple workflows often behave like DAGs
Complete Graph	Rare	Technically possible, but impractical in most AI workflows
Simple Graph	Partially	Possible if no self-loops or repeated transitions are used
Multigraph	Partially	Multiple conditional edges between nodes can simulate multigraph behavior
Bipartite Graph	Possible	Can model two groups of nodes (e.g., agents ↔ tools), though not explicit
Tree	Yes	Many hierarchical workflows naturally form trees

 

Graphs in Code

Eventually, all of these graph concepts must be translated into computer code to make the system work and achieve its objectives. In general, better graph design leads to better workflow organization and more effective agent behavior.

To develop an AI agent using graphs and LangGraph, we also need to understand other components such as:

• state management
• memory
• tools
• prompts
• models
• routing logic

However, for now, here is a simple graph that includes the main components so we can understand how an agent workflow looks structurally.

from langgraph.graph import StateGraph, START, END 
from langgraph.checkpoint.memory import MemorySaver 
from typing import TypedDict 
# STATE 
class AgentState(TypedDict): 
message: str 
retry_count: int 
passed: bool 
# NODES 
def process_node(state: AgentState): 
    print(f"Processing: {state['message']}") 
    return {"retry_count": state["retry_count"] + 1} 
 
def check_node(state: AgentState): 
    print(f"Checking... attempt {state['retry_count']}") 
    passed = state["retry_count"] >= 2 
    return {"passed": passed} 
 
def success_node(state: AgentState): 
    print("Success!") 
    return {} 
 
# CONDITIONAL EDGE function 
def should_retry(state: AgentState): 
    if state["passed"]: 
        return "success" 
    return "retry" 
 
# GRAPH 
builder = StateGraph(AgentState) 
 
# Adding Nodes 
builder.add_node("process", process_node) 
builder.add_node("check", check_node) 
builder.add_node("success", success_node) 
 
# Edges 
builder.add_edge(START, "process")        # Entry Point 
builder.add_edge("process", "check") 
 
# Conditional Edge (with Cycle if retry) 
builder.add_conditional_edges("check", should_retry, { 
    "retry": "process",   # CYCLE — loops back 
    "success": "success"  # moves forward 
}) 
 
builder.add_edge("success", END)          # End Point 
 
# CHECKPOINTER 
checkpointer = MemorySaver() 
graph = builder.compile(checkpointer=checkpointer) 
 
# Run 
config = {"configurable": {"thread_id": "1"}} 
result = graph.invoke({"message": "hello", "retry_count": 0, "passed": False}, config)

A Short History of Graph Theory

Graph Theory began in 1736 with the work of the Swiss mathematician Leonhard Euler. Euler studied a famous problem known as the Seven Bridges of Königsberg, which asked whether it was possible to cross all seven bridges in the city exactly once without repeating a bridge.

Instead of focusing on distances or map shapes, Euler simplified the problem into:

• points (land areas)
• connections (bridges)

This idea became the foundation of graph theory.

During the 19th century, graph theory developed further through studies in:

• networks
• geometry
• topology
• chemistry

Mathematicians began exploring concepts such as:

• trees
• cycles
• paths
• connectivity

In the 20th century, graph theory became an important part of computer science. It was widely used in:

• communication networks
• transportation systems
• electrical circuits
• database design

Today, graph theory plays a major role in modern technologies such as:

• social networks
• internet routing
• search engines
• artificial intelligence
• machine learning

Frameworks like LangGraph apply graph theory concepts to build AI agent workflows, where nodes represent tasks or agents and edges represent execution flow.

Graph theory is now one of the most important mathematical foundations in both computer science and AI systems.