Graph theory

Concepts

• Graph 10 exercisesA graph G is a set V of vertices together with a set E of edges, each formed by two distinct vertices.
• Degree of a vertex 10 exercisesThe degree deg(v) of a vertex v is the number of edges of the graph (the set E) that have it as an endpoint.
• Path in a graph 10 exercisesA path of length k is a sequence of vertices v_0,dots,v_k such that each consecutive pair is joined by an edge of E.
• Connected graph 10 exercisesA graph G=(V,E) is connected if any two vertices u,v∈ V are joined by a path.
• Tree 10 exercisesA tree T=(V,E) is a connected graph that contains no cycles.
• Eulerian cycle 10 exercisesAn Eulerian cycle of a graph G=(V,E) is a cycle that traverses every edge of G exactly once.
• Hamiltonian cycle 10 exercisesA Hamiltonian cycle of a graph G with n≥ 3 vertices is a cycle that visits every vertex of G exactly once.
• Bipartite graph 10 exercisesA bipartite graph is a graph G=(V,E) whose vertices split into two disjoint sets A and B so that every edge e∈ E joins a vertex o…
• Graph coloring 10 exercisesA proper coloring c with k colors of a graph G=(V,E) assigns to each vertex one of the colors 1,dots,k so that no two adjacent ve…
• Planar graph 10 exercisesA planar graph is a graph that can be drawn in the plane with no crossing edges; such a drawing, for v vertices and e edges, spli…