11 Questions
A graph with no ______ or multiple edges is called a simple graph.
loops
Two vertices are ______ if they are the endpoints of an edge.
adjacent
A graph that has an empty vertex and edge set is called a ______ graph.
null
The minimum number of colors needed to color the vertices of a graph is called the ______ number.
chromatic
A sequence of distinct vertices is called a ______.
path
A closed ______ in a graph is called a cycle.
path
A graph with vertex degrees all ______ is called an even graph.
even
A ______ is a list of vertices and edges in a graph.
walk
A graph with an ______ path or circuit has a path that uses every edge exactly once.
Eulerian
The ______ of a graph is the length of the shortest cycle in a graph.
girth
A ______ graph is a simple graph whose vertices are pairwise adjacent.
complete
Study Notes
Graph Basics
- A vertex is a region or object in a graph.
- An edge is a path bridge between regions or a relation between objects in a graph.
- The order of a graph is the number of vertices it has.
- The size of a graph is the number of edges it has.
Edge Characteristics
- A loop is an edge whose endpoints are equal.
- Multiple edges are edges that have the same pair of endpoints.
- A graph is simple if it has no loops or multiple edges.
Vertex Relationships
- Two vertices are adjacent or neighbors if they are the endpoints of an edge.
- A click is a set of pairwise adjacent vertices.
- An independent set is a set of pairwise non-adjacent vertices.
Graph Types
- A finite graph is a graph that has a finite vertex and edge set.
- A null graph is a graph that has an empty vertex and edge set.
- Equivalent graphs are graphs where edges form the same connections of vertices in each graph.
- A bipartite graph is a union of two disjoint independence sets.
Graph Properties
- The chromatic number is the minimum number of colors needed to color the vertices of a graph.
- A path is a sequence of distinct vertices.
- A cycle is a closed path in a graph.
- A graph is connected if there exists at least one path between two vertices.
- A graph is disconnected if there is no path between two vertices.
Vertex Properties
- The degree of a vertex is the number of edges incident upon it.
Special Graphs
- A complete graph is a simple graph whose vertices are pairwise adjacent.
- A complete bipartite graph is a graph where two vertices are adjacent if and only if they are in different partite sets.
- The girth of a graph is the length of the shortest cycle.
Graph Traversal
- A walk is a list of vertices and edges in a graph.
- A trail is a walk in a graph with no repeated edges.
- An even graph is a graph with vertex degrees all even.
- An odd vertex is a vertex whose degree is odd in a graph.
- A graph is traversable if there are no repeating edges.
Eulerian and Hamiltonian Graphs
- A graph is Eulerian if it has an Euler path or circuit.
- A graph is Hamiltonian if a Hamiltonian path passes through all vertices at once.
- An Eulerian circuit is a circuit or trail containing all the edges in a graph.
- An Euler path is a path that uses every edge of a graph exactly once.
Test your understanding of fundamental graph theory concepts, including vertices, edges, order, size, and more.
Make Your Own Quizzes and Flashcards
Convert your notes into interactive study material.
Get started for free
