Graph Terms

1. Define the following terms:
   1. vertex: one of the circles in a graph
   2. edge: a connection between two circles
   3. arc: an edge in a directed graph
   4. adjacent: connected by an edge
   5. incident: an edge and a vertex that are joined
   6. degree of a vertex: the number of edges that touch the vertex
   7. degree sequence: a list of the degrees of the vertices in the graph in non-ascending order.
   8. n-colorable: can be colored with n or fewer colors
   9. subgraph: a subset of the vertex set and edge set of a graph
   10. induced subgraph: there is an edge between any two vertices in the subgraph if and only if there was an edge between them in the graph
   11. planar: can be drawn so no two edges cross each other
   12. bipartite graph: a 2-colorable graph
   13. k-regular: all vertices have degree k
   14. digraph: edges have direction
   15. multigraph: graph with multiple edges between vertices are allowed
   16. pseudograph: multigraph that allows edges from a vertex to itself
   17. chromatic number: fewest number of colors to color a graph
   18. complete graph(clique): a graph with all possible edges
   19. K₁, K₂, K₃, ...: complete graphs with 1 vertex, 2 vertices, 3 vertices, etc.
   20. adjacency matrix: an n by n table where matrix[i][j] represents an edge from vertex i to vertex j.
   21. adjacency lists: for each vertex, a list of its neighbors
   22. walk: a sequence of adjacent vertices
   23. connectivity of a graph: the minimum number of vertices to remove to disconnect the graph.
   24. bridge: an edge that if removed would disconnect the graph.
   25. cut vertex: a vertex that if removed would disconnect the graph.
   26. trail: a walk that doesn't repeat an edge
   27. Euler trail: a trail that uses every edge in the graph
   28. path: a trail that doesn't repeat a vertex
   29. cycle: a path that starts and ends in the same place
   30. degree of a vertex: the number of edges that touch the vertex
   31. tree: a connected, acyclic graph
   32. oriented (or rooted) tree: a hierarchical structured tree.
   33. root: a special node in a tree, drawn at the top
   34. parent: the node directly above a given node in a tree
   35. child: a node directly below a given node in a tree
   36. ancestor: any node above a given node in a tree (on the path from the given node to the root)
   37. descendant: any node below a given node in a tree (on a path from the given node to a leaf)
   38. subtree rooted at vertex v: the portion of the tree that contains v and all of v's descendants
   39. height of a tree: the length of the longest path in the tree from the root to a leaf
   40. binary tree: a tree in which each node may have a left child and a right child
   41. binary search tree: a binary tree in which the left subtree has nodes that are less than a node, and the right subtree has nodes that are greater than the node.
   42. traverse: travel around from node to node using the edges of a graph
   43. depth-first traversal: goes as far as possible before having to back up
   44. breadth-first traversal: visits all vertices at distance 1, then all at distance 2, etc.
   45. independent set of vertices: a set in which no vertex is adjacent to any other
       
   46. isomorphic graphs: two graphs that can have their vertices labeled so that they have the same vertex set and edge set.
   47. Hamiltonian cycle: a cycle that uses all the vertices in the graph.