Grafos - Definição e exemplos básicos
Um grafo é um par de conjuntos $G = (V, A)$ onde os elementos de $V$ são chamados de vértices e os elementos de $A$ são pares de elementos de $V$ (este par pode ou não ser ordenado). Os elemetos de $A$ são chamados de arestas. Quando os elementos de $A$ são ordenados, dizemos que o grafo é orientado.
A menos de menção contrária, quando dizemos grafo, estamos nos referindo a um grafo não orientado, com finitos vértices, sem loops (uma aresta formada por um único vértice) e sem arestas paralelas (todos as arestas são distintas).
Quando fixamos um grafo $G$, sem mencionar quem são seus vértices e arestas, muitas vezes vamos usar a notação $V_G$ e $A_G$ para tais conjuntos respectivamente.
Normalmente representamos um grafo como acima: os vértices são os pontos e as arestas são as linhas conectando tais pontos.
Dizemos que dois vértices $v, w$ são adjacentes se $\{v, w\}$ é uma aresta. Dado um vértice $v$, dentamos por $N(v) = \{w: w$ é adjacente a $v\}$ ($N$ de neighbor). Finalmente, denotamos por $g(v) = |N(v)|$ (grau de $v$).
1 Mostre que a soma de todos os graus de todos os vértices de um grafo é par.
2 Mostre que o total de vértices de grau ímpar é par.
3 Mostre que todo grafo possui dois vértices de mesmo grau.
Dado um grafo $G$, denotamos por $\delta(G) = \min\{d(v): v \in V_G\}$ e por $\Delta(G) = \max\{d(v): v \in V_G\}$.
Dizemos que um grafo é completo se dados quaisquer $v$ e $w$ vértices distintos, temos que eles são adjacentes. Se $G$ tem $n$ vértices e é completo, o denotamos por $K_n$.
4 Quantas arestas tem $K_n$?
Dado $G$ um grafo, definimos o grafo complementar de $G = (V,A)$, denotado por $\bar{G} = (V,A')$, da seguinte maneira: $\{x,y\}\in A'$ se, e somente se, $\{x,y\}\notin A$.
Dados $G = (V_G, A_G)$ e $H = (V_H, A_H)$ grafos, dizemos que $H$ é um subgrafo de $G$ se $V_H \subset V_G$ e $A_H \subset A_G$. Se, além disso, toda aresta ${v, w} \in A_G$ com $v, w \in V_H$ for tal que $\{v, w\} \in A_H$, dizemos que $H$ é um subgrafo induzido.
5 Dê um exemplo de um subgrafo que não seja um subgrafo induzido.
