Dado el grafo G = (V,A) con V = {1,...,6} y A = {{1,2},{1,5},{1,6},
{2,3},{2,4},{2,5},{3,4},{3,6},{4,5},{5,6}}, se pide:
(a) Determinar si G es plano y, si se puede, dibujar una representación plana de G con
aristas rectas.
(b) Obtener la matriz de adyacencia de G.
(c) Determinar si el subgrafo G0 de vértices V 0 = {1,2,3,5} es conexo, usando su matriz de
adyacencia.
(d) Determinar cuántos caminos de longitud 3 hay en G0 entre los vértices 2 y 5.
(e) Determinar si G es euleriano o posee algún camino euleriano.
(f) Si añadimos un séptimo vértice, ¿a cuáles de los seis primeros puede estar unido para
que el nuevo grafo sea euleriano? Hacerlo y construir un circuito euleriano usando el
algoritmo de Fleury.
(g) Determinar si el grafo G es hamiltoniano. Si lo es, buscar un circuito de Hamilton.
(h) Obtener un árbol generador del grafo G.