What is an incident edge?

graph graph-theory terminology
good_evening picture good_evening · Jun 2, 2013 · Viewed 34k times · Source

Two edges of a graph are called adjacent (sometimes coincident) if they share a common vertex. Two arrows of a directed graph are called consecutive if the head of the first one is at the nock (notch end) of the second one. Similarly, two vertices are called adjacent if they share a common edge (consecutive if they are at the notch and at the head of an arrow), in which case the common edge is said to join the two vertices. An edge and a vertex on that edge are called incident.

I don't understand this definition. Could someone give an example of an incident edge? A schematic representation would be helpful.

Answer

stinepike picture stinepike · Jun 2, 2013

Let G = (V, E) be an undirected graph, where V is the set of vertices and E is the set of (undirected) edges. Let u, v ∈ V be vertices of G. Let e = {u, v} ∈ E be an edge of G.

enter image description here

Then e = {u, v} is incident to u and v, or joins u and v. Similarly, u and v are incident to e.

You can have more info at http://www.proofwiki.org/wiki/Definition:Incident.

Related questions

Cycles in an Undirected Graph

Given an undirected graph G=(V, E) with n vertices (|V| = n), how do you find if it contains a cycle in O(n)?

Read More
Difference between hamiltonian path and euler path

Can some one tell me the difference between hamiltonian path and euler path. They seem similar!

Read More
Graphs data structure: DFS vs BFS?

if given a graph problem how do we know whether we need to use bfs or dfs algorithm??? or when do we use dfs algorithm or bfs algorithm. What are the differences and advantages of one over other?

Read More