Teorema: Si G es simple, entonces existen dos vértices del mismo grado

Corolario: El número de vértices de grado impar es par.

Teorema: El diámetro de una gráfica G, es mayor o igual al radio de G y menor o igual al doble del radio de G

Teorema: G es árbol si y solo si G es conexa y su tamaño es igual a su orden menos uno

Teorema: G es árbol si y solo si todo par de vértices tiene una única trayectoria conectándolos

Teorema: Una arista e es un puente si y solo si e no se encuentra en ningún ciclo de G

Teorema: G es bloque si y sólo si para cualquier par de vértices de la gráfica, existe un ciclo que les contiene.

Teorema: G (no trivial) es k conexa, con k mayor o igual a 2, sii para todo par de vértices existen k uv-trayectorias cu

Teorema: Sea G conexa. G es gráfica euleriana sii todo vértice de G tiene grado par

Lema: SI M y M' son apareamientos en G, entonces las componentes conexas de la subgráfica de G inducida por M y M' son c

Teorema (Vizing): Sea G gráfica simple, entonces, su índice cromático es igual al grado máximo de G o el grado máximo+1

Teorema (Fórmula de Euler): Sea G conexa y plana. El orden de G, menos su tamaño, más su número de caras es igual a 2

Teorema: La gráfica completa K_5 y la bipartita completa K_3,3, no son gráficas planas.

Teorema: Toda gráfica plana es 5-coloreable