Tell about an undirected graph and its properties.

An undirected graph is a pair $(V, E)$, where $V$ is a set of vertices (nodes), and $E$ is a set of edges. Each edge is an unordered pair $\{u, v\}$ of vertices $u, v \in V$.

Main properties:

• Undirected edges: The connection between vertices is symmetric. If there is an edge between $u$ and $v$, it means you can move both from $u$ to $v$ and from $v$ to $u$.
• Vertex degree: The number of edges incident to a vertex. Denoted as $deg(v)$.
• Sum of vertex degrees: In any undirected graph, the sum of the degrees of all vertices equals twice the number of edges. $\sum_{v \in V} deg(v) = 2|E|$.
• Path: A sequence of vertices $v_0, v_1, ..., v_k$, where each pair $(v_i, v_{i+1})$ is an edge.
• Cycle: A path that starts and ends at the same vertex, with all other vertices being unique.
• Connectivity: A graph is called connected if there is a path between any pair of vertices. A disconnected graph consists of several connected components.
• Weighted graph: Each edge can be assigned a numerical value (weight).
• Absence of loops and multiple edges (simple graph): In simple undirected graphs, there can be at most one edge between two vertices, and edges do not connect a vertex to itself (no loops).
• Complete graph: A graph in which every pair of distinct vertices is connected by an edge. Denoted as $K_n$, where $n$ is the number of vertices.
• Bipartite graph: The set of vertices can be divided into two disjoint subsets $U$ and $W$, such that each edge connects a vertex from $U$ to a vertex from $W$.