TransWikia.com

Definition of vertex in graph theory

Mathematics Asked on November 20, 2021

What is the definition of vertex in graph theory?
Is it just an endpoint of an edge.If we consider it like that then won’t there be an uncountably many number of vertex in every graph because every point can be considered as a vertex right also won’t there be an uncountably many number of edges?

One Answer

In all definitions of graph I know of (undirected graph, simple graph, directed graph, multigraph, hypergraph) the vertices are dedicated part of the data, ie. in all these cases you start with a set $V$ of vertices, which is then turned into a graph by attaching edges from a set $E$ to these vertices.

Sometimes you can recover the vertices from the set of edges, for example when you have functions $s,t:E rightarrow V$ giving to each edge a source- and a target vertex.

General points of an edge are usually not considered to be a vertex, so if there are finitely many edges you will have finitely many vertices. Yet it is possible to have $V$ being an infinite set (e.g. $Bbb Z=: V$ considered as a graph with an edge between each $n$ and $n+1$) or even $V$ finite and $E$ infinite (e.g. Hawaiian earrings). The standard assumption of combinatorics/graph theory is that $V$ and $E$ are assumed to be finite, though.

Answered by PrudiiArca on November 20, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP