72
$\begingroup$

Okay, so I think if 2 vertices are adjacent to each other, they are incident to each other....or do I have it wrong? Is this just different terminology. I thought I was totally clear on this for my class, but now I am doubting myself reading the book and looking at my notes. I just want to know if I have it correct, and if I don't could someone explain to me what the difference is between the two. I found several wiki's and different university definitions, but none ever said that the two are alike and I'm confused and would like some reassurance. Thanks in advance.

$\endgroup$
106
$\begingroup$

Usually one speaks of adjacent vertices, but of incident edges.

Two vertices are called adjacent if they are connected by an edge.

Two edges are called incident, if they share a vertex.

Also, a vertex and an edge are called incident, if the vertex is one of the two vertices the edge connects.

$\endgroup$
3
  • 20
    $\begingroup$ I would go so far as to say that vertex-edge incidence is the more common usage. $\endgroup$
    – Erick Wong
    Sep 4 '12 at 0:13
  • $\begingroup$ Okay, thank you so much. I am now reviewing what I have and I had thought they were both referring to the vertices for both cases. This makes more sense now. $\endgroup$
    – pqsk
    Sep 4 '12 at 0:19
  • 2
    $\begingroup$ @ErickWong: that seems right, considering objects like the incidence matrix. Thank you for the insight, I will modify my sentence. $\endgroup$ Sep 4 '12 at 0:27
31
$\begingroup$

If for two vertices $A$ and $B$ there is an edge $e$ joining them, we say that $A$ and $B$ are adjacent.

If two edges $e$ and $f$ have a common vertex $A$, the edges are called incident.

If the vertex $A$ is on edge $e$, the vertex $A$ is often said to be incident on $e$.

There is unfortunately some variation in usage. So you need to check the particular book or notes for the definition being used.

$\endgroup$
1
  • $\begingroup$ Thank you for your answer. It makes it more clear. I'm going to mark Bruns' as the answer, since I feel that it was more clear to me, but thank you so much for your input. Very useful as well. $\endgroup$
    – pqsk
    Sep 4 '12 at 0:20
10
$\begingroup$

Excerpted from wikipedia:

  • Two edges of a graph are called adjacent (sometimes coincident) if they share a common vertex.

  • Similarly, two vertices are called adjacent if they share a common edge.

  • An edge and a vertex on that edge are called incident.

This terminology seems very sensible to my ear.

$\endgroup$
1
  • 2
    $\begingroup$ It does to me too now. Lol....my eyes were seeing vertex for everything. I did not realize that for an incident it was referring to the edges. The problem when you are working non-stop day in and day out and then going to school on your off time. :-S $\endgroup$
    – pqsk
    Sep 4 '12 at 0:24
2
$\begingroup$

An edge "e" in a graph (Undirected or directed ) that is associated with the pair of vertices n and q is said to be incident on n and q, and n and q are said to be incident on e and to be adjacent vertices.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.