1.  Introdução

• Um grafo é um um objeto combinatório que consistem em um par G = (V, E) de conjuntos, sendo V um conjunto finito artbitrário e E um conjunto de pares não ordenados de elementos de V. Os elementos de V são chamados vértices e os elementos de E são chamados arestas. Dois vértices v e w são adjacentes (ou vizinhos) se vw é uma aresta.
• Notação:   |G| := |V(G)|   e   ‖G‖ := |E(G)|.
• Segue da definição que grafos não têm laços nem arestas paralelas. Logo, ‖G‖ ≤ (ⁿ₂) < ½ |G|².

1.2  Graus

• d(v) = grau do vértice v
• delta(G) = min d(v) = grau mínimo de G
  Delta(G) = max d(v) = grau máximo de G
  d(G) = 2‖G‖ / |G| = grau médio de G
  
• Um grafo é k-regular se todos os seus vértices têm grau k.  Um grafo com n vértices é completo se for (n − 1)-regular.
• Um grafo H é subgrafo de um grafo G se V(H) ⊆ V(G) e E(H) ⊆ E(G).  Dizemos que H é subgrafo induzido de G se E(H) contém todas as arestas de G que têm ambas as pontas em V(H).
• Proposição 1.2.2:  Existe subgrafo H de G tal que d(H) ≥ d(G) e delta(H) > d(H)/2  (a menos que G não tenha arestas).

1.3  Caminhos e ciclos

• Um caminho é um grafo com conjunto de vértices da forma {1, 2, 3, … , k−1, k} e conjunto de arestas da forma {{1,2}, {2,3}}, … , {k−1, k}} .
• Um ciclo é um grafo com conjunto de vértices da forma {1, 2, 3, … , k−1, k} e conjunto de arestas da forma {{1,2}, {2,3}}, … , {k−1, k}, {k,1}}.   (É claro que k ≥ 3, uma vez que os grafos de Diestel não têm laços nem arestas múltiplas.)
• Um caminho em um grafo é um subgrafo isomorfo a um caminho.  Um ciclo em um grafo é um subgrafo isomorfo a um ciclo.
• Dois grafos G e H são isomorfos se existe uma bijeção entre V(G) e V(H) que preserva a relação de adjacência entre vértices.
• Proposição 1.3.1:  Todo grafo G tem um caminho de comprimento ≥ delta(G)  e  um ciclo de comprimento ≥ delta(G) + 1  (a menos que delta ≤ 1).
• Distância:  d(x,y) = comprimento do menor caminho de x a y.
• Diâmetro:  diam(G) = max d(x,y).
• Raio:  rad(G) = min_x max_y d(x,y), com min sobre x e max sobre y.
• Exercício 1.5:  rad ≤ diam ≤ 2 rad.
• Cintura (= girth):  g(G) = comprimento do menor ciclo.
• Dois caminhos são disjuntos se não têm vértices nem arestas em comum.  Dois caminhos são independentes (= internamente disjuntos) se nenhum contém um vértice interno do outro.  Dois caminhos são disjuntos nas arestas se não têm arestas em comum. 

1.4  Conexidade

• G é conexo se para todo par x,y de vértices existe um caminho que liga x a y.  Um componente de G é qualquer subgrafo conexo maximal de G.
• Proposição 1.4.1:  G conexo  implica  existe enumeração v₁, … , v_n dos vértices tal que G[v₁, v₂] é conexo, G[v₁, v₂, v₃] é conexo, etc.
• Um conjunto X de vértices separa conjuntos de vértices A e B se todo caminho de A a B tem um vértice em X.

  Um conjunto X de vértices e arestas separa conjuntos de vértices A e B se todo caminho de A a B contém um elemento de X.

• X separa G se existem vértices a e b fora de X tais que todo caminho de a a b contém um elemento de X.
• G é k-conexo se tem mais que k vértices e todo separador de G tem menos que k vértices, ou seja, se
  • |G| > k  e 
  • |X| < k  implica  G−X conexo.

  (Definição equivalente:  G é k-conexo se para todo par x,y de vértices existem k caminhos independentes de x a y.  Mas essa equivalência é assunto para o capítulo 3.)

• G é h-aresta-conexo se
  • |G| > 1  e 
  • G−F é conexo para todo conjunto F com menos de h arestas.
• Conexidade:  kappa(G) := menor k tal que G é k-conexo

  lambda(G) := menor h tal que G é h-aresta-conexo

• Exercício 1.10 (conexidade versus grau mínimo):  kappa ≤ lambda ≤ delta.
• Teorema 1.4.2 (Mader) [grau médio versus conexidade]:  d(G) ≥ 4k  implica  subgrafo k-conexo.
• Teorema 1.4.3 (Mader) (da 3a. edição do livro) [grau médio versus conexidade]:  Para qualquer natural não-nulo k, se d(G) ≥ 4k  então  existe subgrafo (k+1)-conexo H de G tal que d(H) > d(G) − 2k.

1.5  Árvores e florestas

• Uma floresta é um grafo acíclico, ou seja, um grafo sem ciclos. Uma árvore é uma floresta conexa.
• Teorema 1.5.1:  T é árvore 
  • se e só se para todo par x, y de vértices existe um único caminho de x a y
  • se e só se T conexo mas T−e não é conexo qualquer que seja e
  • se e só se T acíclico mas T+xy não acíclico para qualquer x e y não adjacentes.
• Corolário 1.5.3:  Se G é árvore  então  ‖G‖ = |G|−1.   Se G é conexo e ‖G‖ = |G|−1  então  G é árvore.
• Se x e y são vértices de uma árvore T então xTy denota o único caminho em T que liga x a y.  Dado um vértice r de uma árvore T, dois vértices x e y são comparáveis em (T, r) se x está em rTy ou y está em rTx.

  Suponha que r é um vértice de uma subárvore T de um grafo G.  O par (T, r) é uma árvore de busca em profundidade (= normal rooted tree = depth-first search tree) se todo par de vértices de T que esteja ligado por um caminho em G sem vértices internos em T é comparável em (T, r).

1.6  Grafos r-partidos

• G é r-partido se existe uma partição V₁, … , V_r de V(G) tal que toda aresta tem uma ponta em algum V_i e outra ponta em V_j para j diferente de i.
• Bipartido é o mesmo que 2-partido.  Um grafo é bipartido completo se tem todas as possíveis arestas.
• Proposição 1.6.1:  G é bipartido  se e só se  G não tem ciclo ímpar.

1.7  Máinors e subcontrações

Grafos dentro de grafos, dentro de grafos, dentro de grafos.

• H é subgrafo de G se V(H) é parte de V(G) e E(H) é parte de E(G).
• H é uma contração de G se o conjunto de vértices de H é uma partição V₁, … , V_k de V(G) tal que  cada G[V_i] é conexo  e  V_i é adjacente a V_j em H se e só se há alguma aresta de V_i a V_j em G.    Os conjuntos V_i são chamados branch sets.
• Caso especial importante: Se e := xy é uma aresta de um grafo G := (V, E), denotamos por  G / e  o grafo que resulta da contração de e.  Esse é o grafo que tem conjunto de vértices (V − {x, y}) ∪ {z}, sendo z um objeto que não está em V, e conjunto de arestas E' ∪ E'' ∪ E''', sendo E' o conjunto das arestas de G sem pontas em comum com e, sendo E'' o conjunto de todos os pares zw tais que xw ∈ E−{e} e sendo E''' o conjunto de todos os pares zw tais que yw ∈ E−{e}.
• H é um máinor (= minor) de G se H é uma contração de algum subgrafo de G.  Diz-se também que H é uma subcontração de G.

  Em outras palavras, H é um máinor de G se o conjunto de vértices de H é uma subpartição V₁, … , V_k de V(G) tal que  cada G[V_i] é conexo  e  V_i é adjacente a V_j em H somente se há alguma aresta de V_i a V_j em G.   (Aqui, uma subpartição de um conjunto V é uma coleção de subconjuntos de V que são dois a dois disjuntos.)

  A expressão H é máinor de G também é usada para dizer que H é isomorfo a um máinor de G.

  Se H é um máinor de G, Diestel diz G inclui um MH.

• Dado um grafo G, seja X um subconjunto de V(G) e suponha que existe uma coleção P de caminhos dois a dois independentes em G sendo que cada caminho tem seus dois extremos em X mas nenhum vértice interno em X.  Nessas condições, um máinor topológico (= topological minor) de G é o grafo H definido da seguinte maneira:  o conjunto de vértices de H é X e dois vértices x e x' são adjacentes em H se e somente se algum elemento de P tem extremos x e x'.

  Se H é máinor topológico de G, Diestel diz G inclui um TH.   Se H é um máinor topológico de G, diz-se que G contém uma subdivisão de H.

  A expressão H é máinor topológico de G também é usada para dizer que H é isomorfo a algum máinor topológico de G.

• Proposição 1.7.2:  Todo máinor topológico é um máinor.   Todo máinor com Delta ≤ 3 é também um máinor topológico.
• Proposição 1.7.3:  A relação é-máinor-de é uma ordem parcial, ou seja, uma relação reflexiva (G é máinor de G), antisimétrica (se F é máinor de G e G é máinor de F então F é isomorfo a G) e transitiva (se F é máinor de G e G é máinor de H então F é máinor de H).  O mesmo vale para a relação é-máinor-topológico-de.

1.8  Trilhas eulerianas

• Passeio (= walk). Passeio fechado.

  Trilha euleriana (= Euler tour): passeio fechado que passa por cada aresta exatamente uma vez.

  Um grafo é euleriano se admite uma trilha euleriana.

• Teorema 1.8.1 (Euler):  Um grafo conexo é euleriano  se e só se  cada um de seus vértices tem grau par.

1.9  Cortes

• Para quaisquer conjuntos X e Y de vértices de um grafo, E(X, Y) é o conjunto de todas as arestas que têm uma ponta em X e outra em Y.
• Um corte (= cut) em um grafo G é qualquer conjunto da forma   E(V₁, V₂)   tal que {V₁, V₂} é uma partição de V(G).

  Exemplo: para qualquer vértice v, o conjunto E({v}, V − {v}) é um corte.

• Uma ponte (= bridge), ou aresta de corte, é qualquer aresta e tal que {e} é um corte.

1.10  Multigrafos

• Um multigrafo é um grafo generalizado que admite arestas paralelas e laços.

  Duas arestas de um mutigrafo são paralelas se têm as mesmas pontas. Uma laço é uma arestas cujas pontas são idênticas.