G is a graph with n vertices. Prove that $χ(G) · χ( \overline G) ≥ n$.
38700
the Nordhaus-Gaddum problems for chromatic number of graph and its complement
157939
prove that a graph is one-ended
129845
Prove that $T$ is a subgraph of $G$
7626
Proving that every connected graph has a vertex whose removal will not disconnect the graph.
154564
Prove that the sum of minimum edge cover and maximum matching is the vertex count
35800
If $K \leq H \leq G$, show that $[G:K] = [G:H][H:K]$.
59247
How many connected graphs over V vertices and E edges?
150508
∗∗Prove that each graph with an even number of vertices has two vertices with an even number of common neighbors.
115085
number of vertices in a self-complemntary graph
67887
Prove that a graph on $n$ vertices with girth $g$ has at most $\frac{g}{g-2}(n-2)$ edges
93304
How to prove Graph with $n$ vertices has Edge Chromatic Number no more than $n/2$ edges
139657
Prove that if $\chi(G-u-v)=\chi(G)-2$ for every vertices $u, v$ ($u \ne v$) then G is complete graph.
65096
$\chi(G)+\chi(G')\leq n+1$
27373
Graph Proof by induction.
31854
Proof - raising adjacency matrix to $n$-th power gives $n$-length walks between two vertices
86635
Optimizing $(X_{n}+c)^{2}$ to show that $P(\overline{X}_{n}\geq \lambda) \leq E(X_{n}^{2})/(EX_{n}^{2}+ \lambda^{2})$
33316
Show that if $G$ is simple a graph with $n$ vertices and 􏰈the number of edges $m>\binom{n-1}{2}$, then $G$ is connected.