# 6. Control questions and tasks / Контрольні запитання і завдання

## Graphs and degree

1. Define a **graph**, and the terms **adjacent** and **incident**. What makes a
   graph **simple**?
2. Define the **degree** of a vertex. State the **handshaking theorem** and
   explain why it holds.
3. Why must the number of vertices of **odd degree** be even?

## Representations

4. Define the **adjacency matrix**. Why is it symmetric for an undirected graph?
   Write it for $V = \{1,2,3\}$, $E = \{(1,2),(2,3)\}$.
5. Define the **incidence matrix**. How many $1$s are in each column, and why?
   Write it for $V = \{A,B,C\}$, $E = \{(A,B),(B,C)\}$.

## Walks, paths, subgraphs, isomorphism

6. Distinguish a **walk**, a **trail**, a **path**, and a **circuit**. Why can the
   number of walks between two vertices be infinite?
7. When is $H$ a **subgraph** of $G$? Give the conditions on its vertices and
   edges.
8. Define graph **isomorphism**. Name three **invariants** that isomorphic graphs
   must share, and explain how they help reject a non-isomorphic pair quickly.

## Implementation and complexity

9. Describe how **depth-first search** finds a path between two vertices. What is
   its time complexity in terms of $|V|$ and $|E|$?
10. Why is enumerating **all** simple paths, or testing **isomorphism**, expensive
    in the worst case?

## Tasks by hand

11. For $V = \{1,2,3,4\}$, $E = \{(1,2),(2,3),(3,4),(4,1),(1,3)\}$, compute the
    degree of every vertex and verify the handshaking theorem.
12. Write the adjacency matrix of the graph in question 11.
13. List two distinct **simple paths** from vertex $1$ to vertex $4$ in that
    graph.