Graph Theory Fundamental - Terms

Point

A particular position in space, represented by a dot and labeled by an alphabet, number, or alphanumeric value.

False

True or False:

A point can only be labeled with numbers.

Line

A connection between two points, represented by a solid line.

False

True or False:

A line can exist without connecting two points.

Vertex

A synonym for a point in a graph; also called "node," "point," or "junction."

False

True or False:

A vertex cannot be labeled with numbers.

Edge (Link)

A connection between two vertices; can be directed (with direction) or undirected (no direction).

True

True or False:

An undirected edge is the same as two directed edges (A→B and B→A).

Null Graph

A graph with no edges between its vertices (also called an empty graph).

False

True or False:

A null graph must have at least one edge.

Trivial Graph

A graph with only one vertex and no edges.

False

True or False:

A trivial graph can have multiple vertices.

Simple Graph

An undirected graph with no parallel edges or loops.

False

True or False:

A simple graph can have loops.

Complete Graph

A graph where every pair of vertices is joined by exactly one edge.

False

True or False:

In a complete graph, not all vertices need to be connected.

Connected Graph

A graph where a path exists between every pair of vertices.

True

True or False:

A disconnected graph has at least one isolated vertex.

Regular Graph

A graph where all vertices have the same degree (e.g., 2-regular).

False

True or False:

In a 3-regular graph, one vertex can have degree 2.

Cyclic Graph

A graph containing at least one cycle (a closed path with no repeated vertices).

True

True or False:

A cycle graph with 3 vertices has 3 edges.

Acyclic Graph

A graph with no cycles (e.g., a tree).

True

True or False:

All trees are acyclic graphs.

Bipartite Graph

A graph whose vertices can be split into two disjoint sets where edges only connect vertices from different sets.

False

True or False:

A bipartite graph can have edges within the same set.

Complete Bipartite Graph

A bipartite graph where every vertex in one set is connected to every vertex in the other set.

Star Graph

A complete bipartite graph where one vertex connects to all others (e.g., SnSn​).

Weighted Graph

A graph with numerical labels (weights) assigned to edges.

Multi-graph

A graph with multiple edges between vertices or loops.

False

True or False:

The length of a path in a weighted graph is the number of edges.

False

True or False:

A simple graph is a type of multi-graph.

Planar Graph

A graph that can be drawn on a plane without edge crossings.

False

True or False:

K5​ (complete graph with 5 vertices) is planar.

Non-Planar Graph

A graph that cannot be drawn without edge crossings.

False

True or False:

All trees are non-planar.

Loop

An edge connecting a vertex to itself.

False

True or False:

Loops are allowed in simple graphs.

Parallel Edges

Multiple edges connecting the same pair of vertices.

True

True or False:

Parallel edges are allowed in multi-graphs.

Null Graph

What type of Graph is this?

Trivial Graph

What type of Graph is this?

Simple Graph

What type of Graph is this?

Undirected Graph

What type of Graph is this?

Directed Graph

What type of Graph is this?

Complete Graph

What type of Graph is this?

Connected Graph

What type of Graph is this?

Disconnected Graph

What type of Graph is this?

Regular Graph

What type of Graph is this?

Cyclic Graph

What type of Graph is this?

Acyclic Graph

What type of Graph is this?

Bipartite Graph

What type of Graph is this?

Complete Bipartite Graph

What type of Graph is this?

Star Graph

What type of Graph is this?

Weighted Graph

What type of Graph is this?

Multi-graph

What type of Graph is this?

Planar Graph

What type of Graph is this?

Non - Planar Graph

What type of Graph is this?