Glossary

2.1 Vertices, edges, and degree

2 min read•july 24, 2024

Graphs are made up of vertices and edges, representing entities and their connections. Understanding these components is crucial for analyzing network structures in various fields, from social networks to transportation systems.

properties, like , provide insights into a graph's structure. Degree measures a vertex's connectivity, while concepts like indegree and outdegree in directed graphs reveal the flow of information or resources within a network.

Graph Components and Vertex Properties

Vertices and edges

Top images from around the web for Vertices and edges

  • CS 360: Lecture 15: Graph Theory View original

    Is this image relevant?

  • Graph Theory Basics | Mathematics for the Liberal Arts View original

    Is this image relevant?

  • CS 360: Lecture 15: Graph Theory View original

    Is this image relevant?

1 of 3

Top images from around the web for Vertices and edges

  • CS 360: Lecture 15: Graph Theory View original

    Is this image relevant?

  • Graph Theory Basics | Mathematics for the Liberal Arts View original

    Is this image relevant?

  • CS 360: Lecture 15: Graph Theory View original

    Is this image relevant?

1 of 3
  • Vertices (nodes) form fundamental elements representing entities or points depicted as dots or circles (cities in a transportation network)
  • Edges connect vertices representing relationships or links typically shown as lines or arrows (roads connecting cities)
  • Graph notation expressed as [G = (V, E)](https://www.fiveableKeyTerm:g_=_(v,_e)) where VV represents set of vertices and EE represents set of edges
  • Types of graphs based on properties include undirected graphs with no directional edges and directed graphs (digraphs) with specific directional edges (social network connections vs one-way streets)

Degree of a vertex

  • Degree defines number of edges incident to a vertex denoted as deg(v)deg(v) for a vertex vv
  • Degree properties range from minimum degree 0 for isolated vertices to maximum degree ∣V∣−1|V| - 1 for vertices connected to all others
  • states sum of degrees of all vertices equals twice the number of edges: ∑v∈Vdeg(v)=2∣E∣\sum_{v \in V} deg(v) = 2|E|
  • lists vertex degrees in non-increasing order
  • feature all vertices with same degree (cube graph)

Calculating vertex degrees

  • Simple graph examples:
    • end vertices have degree 1 others have degree 2
    • all vertices have degree 2
    • KnK_n all vertices have degree n−1n-1
  • Special graph structures:
    • central vertex has degree n−1n-1 others have degree 1
    • central vertex has degree n−1n-1 others have degree 3
  • may have different degrees for vertices in each partition
  • count multiple edges between same pair of vertices
  • contribute 2 to degree of vertex

Indegree vs outdegree

  • Indegree counts number of edges pointing towards a vertex denoted as deg−(v)deg^-(v) (incoming emails)
  • Outdegree counts number of edges pointing away from a vertex denoted as deg+(v)deg^+(v) (outgoing emails)
  • Total degree in directed graphs sums indegree and outdegree: deg(v)=deg−(v)+deg+(v)deg(v) = deg^-(v) + deg^+(v)
  • have equal indegree and outdegree
  • have indegree 0 while have outdegree 0 (starting and ending points in a flow network)
  • properties: sum of all indegrees equals sum of all outdegrees both equaling total number of edges in graph

Key Terms to Review (29)

Adjacent Vertices: Adjacent vertices are pairs of vertices in a graph that are connected directly by an edge. Understanding the concept of adjacent vertices is crucial as it relates to the overall structure of a graph, influencing properties such as degree, connectivity, and traversal methods. The relationships between adjacent vertices play a significant role in defining various graph types and can affect calculations related to graph distance and colorings.
Balanced Vertices: Balanced vertices are vertices in a graph that maintain an equal distribution of connections to other vertices, specifically in terms of their degrees. This concept is significant when analyzing the structure and behavior of a graph, as balanced vertices can lead to more stable configurations and affect the overall properties of the graph, such as connectivity and flow.
Bipartite Graphs: Bipartite graphs are a special type of graph that can be divided into two distinct sets of vertices such that no two vertices within the same set are adjacent. This property makes them useful in modeling relationships between two different groups, like students and courses or jobs and applicants. The visualization of bipartite graphs can often reveal insights into connections and structures that are not apparent in regular graphs.
Complete Graph: A complete graph is a type of graph in which every pair of distinct vertices is connected by a unique edge. This means that in a complete graph, there are no missing connections, making it a fully connected structure. Complete graphs are crucial for understanding various concepts in graph theory, including the relationships between vertices, edge connectivity, and properties relevant to specific paths and circuits.
Complete Graph k_n: A complete graph, denoted as $$K_n$$, is a type of graph in which every pair of distinct vertices is connected by a unique edge. This means that in a complete graph with $$n$$ vertices, there are no missing edges between any two vertices, resulting in the maximum number of edges possible for that number of vertices. This structure leads to interesting properties related to the number of edges and degrees of the vertices, as every vertex has the same degree.
Connected Graph: A connected graph is a type of graph in which there is a path between every pair of vertices. This means that starting from any vertex, you can reach any other vertex by traversing the edges of the graph, ensuring that all vertices are part of a single connected component.
Cycle Graph: A cycle graph is a type of graph that consists of a single cycle, meaning it is a closed loop where each vertex is connected in a circular manner with edges. In a cycle graph, the vertices can be visited in such a way that you can return to the starting point without retracing any edge. This concept connects to understanding the relationships between vertices and edges, as well as how these elements play into coloring problems, particularly with regard to chromatic numbers and vertex coloring strategies.
Degree: In graph theory, the degree of a vertex is defined as the number of edges incident to it. This measurement is crucial because it provides insight into the connectivity and structure of a graph. A high degree indicates that a vertex has many connections, which can influence how information or resources flow within networks, while a low degree suggests fewer connections. Understanding degree also helps in classifying graph types and analyzing complex systems like transportation and communication networks.
Degree Sequence: A degree sequence is a list of the degrees of each vertex in a graph, typically arranged in non-increasing order. It serves as a fundamental concept in understanding the structure of graphs, providing insights into the connectivity and overall properties of the graph. The degree sequence can help identify potential graph configurations and determine whether a particular sequence can represent a simple graph.
Directed graph: A directed graph, or digraph, is a set of vertices connected by edges where each edge has a direction associated with it, indicating the relationship between the vertices. This directionality means that if there is an edge from vertex A to vertex B, it does not imply there is an edge from B to A, which allows for a more complex representation of relationships. Directed graphs are essential in understanding concepts like connectivity, flow, and pathways in various applications including computer networks and social networks.
Edge: In graph theory, an edge is a connection between two vertices in a graph. Edges can represent relationships or pathways between the vertices, and they play a critical role in determining the structure and properties of the graph. Understanding edges helps to explore concepts such as connectivity, traversal, and network flow within graphs.
Euler's Theorem: Euler's Theorem states that in a connected graph, there exists an Eulerian circuit if and only if every vertex has an even degree, and there exists an Eulerian trail if exactly two vertices have an odd degree. This theorem highlights the relationship between the degrees of vertices and the existence of specific paths within graphs, connecting the concept of edges and vertices with important traversability properties.
G = (v, e): In graph theory, a graph is represented as g = (v, e), where 'v' denotes the set of vertices and 'e' represents the set of edges connecting those vertices. This notation encapsulates the fundamental structure of a graph, illustrating how vertices interact through edges. Understanding this representation is crucial for analyzing various properties of graphs, such as connectivity and traversal, as well as for exploring concepts like covers and matchings in more complex scenarios.
Handshaking Lemma: The Handshaking Lemma is a fundamental principle in graph theory stating that in any undirected graph, the sum of the degrees of all vertices is twice the number of edges. This arises because each edge contributes to the degree of two vertices, creating a clear relationship between vertices, edges, and their respective degrees.
In-degree: In-degree is a fundamental concept in graph theory that refers to the number of edges directed into a vertex. It helps in understanding the flow of information or connections in a directed graph, where each edge has a specific direction. In-degree is essential for analyzing the relationships between vertices, as it can indicate how many other vertices influence a particular vertex in a network.
Incident Edges: Incident edges are the edges of a graph that connect to a particular vertex. In graph theory, understanding incident edges is essential as they directly relate to the concepts of vertices and the degree of a vertex, which indicates how many edges are connected to it. The relationship between incident edges and vertices plays a crucial role in determining the structure and properties of graphs.
Isolated Vertex: An isolated vertex is a vertex in a graph that has no edges connected to it, meaning its degree is zero. This lack of connections distinguishes it from other vertices and plays a significant role in understanding the overall structure of the graph. Isolated vertices can impact various properties of graphs, including their connectivity and how they relate to other vertices.
Loops: Loops are edges in a graph that connect a vertex to itself, essentially creating a single edge that starts and ends at the same point. This unique feature plays a significant role in understanding the overall structure of a graph, as they contribute to the degree of the vertex they connect to. In many cases, loops can affect properties like connectivity and can be crucial when analyzing graphs for specific applications.
Multigraphs: A multigraph is a type of graph that allows multiple edges between the same pair of vertices. This means that if two vertices are connected by more than one edge, those edges are all included in the multigraph, enabling a richer representation of relationships between vertices. Multigraphs can also include loops, which are edges that connect a vertex to itself, further expanding their versatility in modeling various situations.
Out-degree: Out-degree is a concept in graph theory that refers to the number of edges directed away from a particular vertex in a directed graph. It is an essential measure that helps to analyze the connectivity and influence of a vertex within the graph, showing how many other vertices it can reach directly. Understanding out-degree allows for insights into the structure of the graph, including how information or resources might flow from one point to another.
Path Graph: A path graph is a specific type of graph that consists of a sequence of vertices where each vertex is connected by exactly one edge to the next vertex in the sequence. This structure creates a linear arrangement of vertices, with two endpoints and a series of intermediate vertices. Path graphs are fundamental in understanding key concepts like degree of vertices, tree structures, and properties related to Eulerian circuits and trails.
Pendant Edge: A pendant edge is an edge in a graph that connects a vertex of degree one to another vertex. This means that one end of the edge is attached to a vertex that has no other connections besides this single edge. Pendant edges are important as they highlight simple relationships in graph structures and contribute to the overall degree of connectedness among vertices.
Regular Graphs: A regular graph is a type of graph where each vertex has the same degree, meaning every vertex connects to the same number of edges. This uniformity leads to interesting properties in their structure and behavior, making regular graphs a significant concept in understanding vertex connectivity and edge distribution. Regular graphs can be classified into different types based on their degree, such as k-regular graphs, where every vertex has a degree of k.
Sink vertices: Sink vertices, also known as sink nodes, are specific types of vertices in directed graphs that have incoming edges but no outgoing edges. These vertices serve as endpoints within the structure of a graph, often representing final destinations or conclusions in various applications. Their importance lies in their role in determining the flow of information or resources through the graph, as they indicate where inputs converge without any further output.
Source vertices: Source vertices are those vertices in a directed graph that have no incoming edges. This means that they do not receive any connections from other vertices, making them the starting points or origins of directed paths within the graph. Source vertices are essential for understanding the flow of information or resources in directed graphs, as they can initiate processes or pathways to other vertices.
Star graph: A star graph is a specific type of graph that consists of one central vertex connected directly to several outer vertices, forming a star-like shape. This structure highlights the concept of connectivity and the relationships between vertices, as the central vertex serves as a hub while all other vertices are leaves with only one edge connecting them to the center. The degree of the central vertex is equal to the number of outer vertices, while all other vertices have a degree of one.
Undirected Graph: An undirected graph is a set of vertices connected by edges, where the edges do not have a direction. This means that if there is an edge between two vertices, it can be traversed in both directions, making it possible to move back and forth between those vertices. Undirected graphs are important because they can represent relationships where the order of connection doesn’t matter, such as friendships or collaborations.
Vertex: A vertex is a fundamental unit in graph theory, representing a point where edges meet or connect. In a graph, vertices serve as the nodes that signify various entities, while the edges indicate the relationships or connections between them. Understanding vertices is crucial as they play a key role in determining the structure, properties, and behavior of different types of graphs.
Wheel graph: A wheel graph is a type of graph that consists of a central vertex connected to all vertices of a cycle. It can be visualized as a circle with a hub in the center, where the hub connects to each point on the circle. The wheel graph is notable for its distinct structure that includes both a cycle and spokes, making it an interesting example of how vertices and edges can interact in unique ways.
© 2024 Fiveable Inc. All rights reserved.
AP® and SAT® are trademarks registered by the College Board, which is not affiliated with, and does not endorse this website.
Back
Practice QuizGlossary
Practice QuizGlossary
Next guide