Vertex (graph theory)

<h2 id="types-of-vertices">Types of vertices</h2>

<p>The <a href="/facts/Degree_(graph_theory)/LnFFpI8v">degree</a> of a vertex, denoted 𝛿(v) in a graph is the number of edges incident to it. An isolated vertex is a vertex with degree zero; that is, a vertex that is not an endpoint of any edge (the example image illustrates one isolated vertex).<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a> A leaf vertex (also pendant vertex) is a vertex with degree one. In a directed graph, one can distinguish the outdegree (number of outgoing edges), denoted 𝛿 +(v), from the indegree (number of incoming edges), denoted 𝛿−(v); a source vertex is a vertex with indegree zero, while a sink vertex is a vertex with outdegree zero. A simplicial vertex is one whose <a href="/facts/Neighborhood_(graph_theory)/E6V1hk6b">closed neighborhood</a> forms a <a href="/facts/Clique_(graph_theory)/XK9ppLz5">clique</a>: every two neighbors are adjacent. A <a href="/facts/Universal_vertex/5YRHn7Y2">universal vertex</a> is a vertex that is adjacent to every other vertex in the graph.
</p><p>A <a href="/facts/Cut_vertex/Y4221AkA">cut vertex</a> is a vertex the removal of which would disconnect the remaining graph; a <a href="/facts/Vertex_separator/JcBrRzQe">vertex separator</a> is a collection of vertices the removal of which would disconnect the remaining graph into small pieces. A <a href="/facts/K-vertex-connected_graph/EST9uf8W">k-vertex-connected graph</a> is a graph in which removing fewer than <i>k</i> vertices always leaves the remaining graph connected. An <a href="/facts/Independent_set_(graph_theory)/ksu46kdz">independent set</a> is a set of vertices no two of which are adjacent, and a <a href="/facts/Vertex_cover/WK86bJvf">vertex cover</a> is a set of vertices that includes at least one endpoint of each edge in the graph. The <a href="/facts/Vertex_space/CPmF0hdD">vertex space</a> of a graph is a vector space having a set of basis vectors corresponding with the graph's vertices.
</p><p>A graph is <a href="/facts/Vertex-transitive_graph/042b7rD7">vertex-transitive</a> if it has symmetries that map any vertex to any other vertex. In the context of <a href="/facts/Graph_enumeration/3AgPDEAV">graph enumeration</a> and <a href="/facts/Graph_isomorphism/SBjVIhwW">graph isomorphism</a> it is important to distinguish between labeled vertices and unlabeled vertices. A labeled vertex is a vertex that is associated with extra information that enables it to be distinguished from other labeled vertices; two graphs can be considered isomorphic only if the correspondence between their vertices pairs up vertices with equal labels. An unlabeled vertex is one that can be substituted for any other vertex based only on its <a href="/facts/Adjacency_(graph_theory)/W0MqKkyE">adjacencies</a> in the graph and not based on any additional information.
</p><p>Vertices in graphs are analogous to, but not the same as, <a href="/facts/Vertex_(geometry)/ID3cea9z">vertices of polyhedra</a>: the <a href="/facts/Skeleton_(topology)/EAt2F7tC">skeleton</a> of a polyhedron forms a graph, the vertices of which are the vertices of the polyhedron, but polyhedron vertices have additional structure (their geometric location) that is not assumed to be present in graph theory. The <a href="/facts/Vertex_figure/3u2ySK0C">vertex figure</a> of a vertex in a polyhedron is analogous to the neighborhood of a vertex in a graph.
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Node_(computer_science)/eYlvVE0z">Node (computer science)</a></li>
<li><a href="/facts/Graph_theory/VVPCd4TX">Graph theory</a></li>
<li><a href="/facts/Glossary_of_graph_theory/W0MqKkyE">Glossary of graph theory</a></li></ul>

<ul><li>Gallo, Giorgio; Pallotino, Stefano (1988). "Shortest path algorithms". <i>Annals of Operations Research</i>. 13 (1): 1–79. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2FBF02288320">10.1007/BF02288320</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:62752810">62752810</a>.</li>
<li><a href="/facts/Claude_Berge/VPsApqnu">Berge, Claude</a>, <i>Théorie des graphes et ses applications</i>. Collection Universitaire de Mathématiques, II Dunod, Paris 1958, viii+277 pp. (English edition, Wiley 1961; Methuen & Co, New York 1962; Russian, Moscow 1961; Spanish, Mexico 1962; Roumanian, Bucharest 1969; Chinese, Shanghai 1963; Second printing of the 1962 first English edition. Dover, New York 2001)</li>
<li><a href="/facts/Gary_Chartrand/bYsya9Nf">Chartrand, Gary</a> (1985). <a href="https://archive.org/details/introductorygrap0000char"><i>Introductory graph theory</i></a>. New York: Dover. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-486-24775-9.</li>
<li>Biggs, Norman; Lloyd, E. H.; Wilson, Robin J. (1986). <a href="/facts/Graph_Theory,_1736%E2%80%931936/hIQBAkgf"><i>Graph theory, 1736-1936</i></a>. Oxford [Oxfordshire]: Clarendon Press. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-19-853916-9.</li>
<li><a href="/facts/Frank_Harary/3J2P7l4w">Harary, Frank</a> (1969). <i>Graph theory</i>. Reading, Mass.: Addison-Wesley Publishing. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-201-41033-8.</li>
<li>Harary, Frank; Palmer, Edgar M. (1973). <i>Graphical enumeration</i>. New York, Academic Press. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-12-324245-2.</li></ul>
<h2 id="external-links">External links</h2>
<ul><li><a href="/facts/Eric_W._Weisstein/FbMuVDep">Weisstein, Eric W.</a> <a href="https://mathworld.wolfram.com/GraphVertex.html">"Graph Vertex"</a>. <i><a href="/facts/MathWorld/yc1jodbq">MathWorld</a></i>.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>File:Small Network.png; example image of a network with 8 vertices and 10 edges <a href="/wiki/File:Small_Network.png" target="_blank">/wiki/File:Small_Network.png</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
</ol>

Vertex (graph theory) open-in-new

Vertex (graph theory)