Discover published sets by community

Every planar graph can be colored with at most four colors in such a way that no two adjacent vertices have the same color.

A sequence of non-negative integers can be the degree sequence of a simple graph if and only if the sum of the sequence is even and does not violate Erdős–Gallai inequality.

The number of trees on $n$ labeled vertices is $n^{n-2}$.

Given a graph with weighted edges and a single source vertex, Dijkstra's algorithm computes the shortest path from the source to all other vertices in the graph.

For any finite, connected, planar graph, $V - E + F = 2$, where $V$ is the number of vertices, $E$ is the number of edges, and $F$ is the number of faces.

A method for finding an Eulerian path or circuit, which starts at any vertex and follows edges through every vertex of the graph exactly once.

In any undirected graph, the sum of the degrees of all vertices is equal to twice the number of edges: $\sum_{v \in V} \deg(v) = 2|E|$.

In a bipartite graph, the number of edges in a maximum matching is equal to the number of vertices in a minimum vertex cover.

For any given integers $r$ and $s$, there exists a minimum integer $N$ such that any graph of at least $N$ vertices will contain either a complete subgraph of $r$ vertices or an independent set of $s$ vertices.

The chromatic index of a simple graph $G$ (i.e., the minimum number of colors needed to color the edges of $G$ such that no two adjacent edges have the same color) is either equal to its maximum degree $\Delta$ or to $\Delta + 1$.

Given a bipartite graph, there exists a matching that matches all vertices of the left set to distinct vertices in the right set if and only if for every subset of vertices of the left set, the number of neighbors is at least the number of vertices in the subset.