09 Introduction to Graph Theory Free Online FlashCards

What is a graph in graph theory?

A graph is written as $G=(V,E)$, where $V$ contains vertices and $E$ contains edges joining pairs of vertices.

What does the order of a graph measure?

The order of a graph is $|V|$, the number of vertices.

What does the size of a graph measure?

The size of a graph is $|E|$, the number of edges.

Which representation lists each vertex’s neighbors?

An adjacency list records the neighbors of each vertex and is usually efficient for sparse graphs.

What special property does an undirected graph’s adjacency matrix have?

For an undirected graph, the adjacency matrix is symmetric because adjacency from one vertex to another is mutual.

What is the degree of a vertex?

The degree $\deg(v)$ is the number of edges incident with vertex $v$. A loop contributes 2.

State the Handshaking Lemma.

The Handshaking Lemma states $\sum_{v\in V}\deg(v)=2|E|$ for every finite undirected graph.

What is a walk?

A walk is a vertex sequence in which consecutive vertices are adjacent; vertices and edges may repeat.

What distinguishes a trail from a walk?

A trail is a walk that does not repeat edges; vertices may still repeat.

What is a path?

A path is a walk that does not repeat vertices.

What is a cycle?

A cycle is a closed path that begins and ends at the same vertex, with no other vertex repeated.

When is a graph connected?

A graph is connected when every pair of vertices has a path between them.