Graph theory basics flashcards

Question 1

What is a graph $G=(V,E)$?

Accepted Answer

A graph is an ordered pair $G=(V,E)$ where $V$ is a set of vertices (nodes) and $E$ is a set of edges, each edge joining two vertices (in an undirected graph, an edge is an unordered pair $\{u,v\}$).

Question 2

What is the difference between a walk, a path, and a cycle?

Accepted Answer

A walk may repeat vertices/edges. A path is a walk with no repeated vertices. A cycle is a closed path (start = end) with no repeated vertices except the first/last.

Question 3

What does it mean for a graph to be planar, and what is Euler's formula for connected planar graphs?

Accepted Answer

Planar means it can be drawn in the plane with no edge crossings (except at vertices). For a connected planar embedding, $$V-E+F=2,$$ where $F$ is the number of faces (including the outer face).

Graph theory basics flashcards

Master Math with AI

Learning Resources

Trusted & Recognized