prove that a graph with degree $\frac{n-1}{2}$ has a diameter of at most 2
87760
Determine the diameter of a graph of order $n \geq 3$ where $\delta (G) \geq \frac{n-1}{2}$.
141184
Proof that a degree 4 polynomial has at least two roots
49193
Constructing a graph from a degree sequence
118916
How do I prove that a polynomial F[x] of degree n has at most n roots
83036
f(g(x)) has a degree divisible by n
94838
Show that a self-complementary graph contains an odd number of vertices with degree $(n-1)/2$
126428
Prove the edges of a multigraph may be oriented such that the net-degree of any vertex is $\leq 1$.
46309
Prove that this graph is nonplanar
117685
Prove that a bipartite planar graph has a vertex of degree at most 3
123742
Proving connectedness of the $n$-sphere
13226
If $n$ is a natural number $\ge 2$ how do I prove that any graph with $n$ vertices has at least two vertices of the same degree?
99746
Vertex cover in a graph with maximum degree of 3 and average degree of 2.
129752
How to find whether it is possible for each vertex of a graph to have a different degree?
138601
There are $2n+1$ people. For each $n$ people there is somebody who is friend with each of them. Prove there is a "know-them-all" person.
35458
Prove, that graph $G$ has at least $\chi(G)(\chi(G)-1)/2$ edges.
82578
Show that if $G$ is $2-$connected, then for any two vertices $u$ and $v$ there exists a cycle $C$ such that $u, v \in V (C)$
75461
If $n>m$, then the number of $m$-cycles in $S_n$ is given by $\frac{n(n-1)(n-2)\cdots(n-m+1)}{m}$.