- K-vertex-connected graph
In

graph theory , a graph "G" with vertex set "V(G)" is said to be**"k"-vertex-connected**(or**"k"-connected**) if $G\; setminus\; X$ is connected for all $X\; subseteq\; V(G)$ with $left|\; X\; ight|\; <\; k$. In plain English, a graph is "k"-connected if the graph remains connected when you delete fewer than "k" vertices from the graph. Or, equivalently (owing toMenger's theorem ), a graph is "k"-connected if any two of its vertices can be joined by "k" independent paths Harv|Diestel|2005| p=55.A 1-vertex-connected graph is connected, while a 2-vertex-connected graph is said to be biconnected.

If a graph "G" is "k"-vertex-connected, and "k" < |"V(G)"|, then $k\; le\; delta(G)$, where "δ(G)" is the minimum degree of any vertex $v\; in\; V(G)$. This fact is clear since deleting all neighbors of a vertex of minimum degree will disconnect that vertex from the rest of the graph.

The 1-skeleton of any "k"-dimensional convex

polytope forms a $k$-vertex-connected graph (Balinski 1961). As a partial converse, Steinitz showed that any 3-vertex-connectedplanar graph forms the skeleton of a convexpolyhedron .**References***cite journal

author = Balinski, M. L.

title = On the graph structure of convex polyhedra in "n"-space

journal =Pacific Journal of Mathematics

volume = 11

issue = 2

year = 1961

pages = 431–434

url = http://www.projecteuclid.org/Dienst/UI/1.0/Summarize/euclid.pjm/1103037323*.

**See also***

k-edge-connected graph

*Connectivity (graph theory)

*Menger's theorem

*Structural cohesion

*Wikimedia Foundation.
2010.*

### Look at other dictionaries:

**K-edge-connected graph**— In graph theory, a graph G with edge set E(G) is said to be k edge connected if G setminus X is connected for all X subseteq E(G) with left| X ight| < k. In plain English, a graph is k edge connected if the graph remains connected when you delete … Wikipedia**Graph (mathematics)**— This article is about sets of vertices connected by edges. For graphs of mathematical functions, see Graph of a function. For statistical graphs, see Chart. Further information: Graph theory A drawing of a labeled graph on 6 vertices and 7 edges … Wikipedia**Vertex (graph theory)**— For other uses, see Vertex (disambiguation). A graph with 6 vertices and 7 edges where the vertex number 6 on the far left is a leaf vertex or a pendant vertex In graph theory, a vertex (plural vertices) or node is the fundamental unit out of… … Wikipedia**Graph toughness**— In graph theory, toughness is a measure of the connectivity of a graph. A graph G is said to be t tough if, for every k > 1, G cannot be split into k different connected components by the removal of fewer than tk vertices. For instance, a graph… … Wikipedia**graph theory**— Math. the branch of mathematics dealing with linear graphs. [1965 70] * * * Mathematical theory of networks. A graph consists of nodes (also called points or vertices) and edges (lines) connecting certain pairs of nodes. An edge that connects a… … Universalium**Graph of groups**— In geometric group theory, a graph of groups is an object consisting of a collection of groups indexed by the vertices and edges of a graph, together with a family of injective homomorphisms of the edge groups into the vertex groups.There is a… … Wikipedia**Connected component (graph theory)**— A graph with three connected components. In graph theory, a connected component of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices. For example,… … Wikipedia**Graph theory**— In mathematics and computer science, graph theory is the study of graphs : mathematical structures used to model pairwise relations between objects from a certain collection. A graph in this context refers to a collection of vertices or nodes and … Wikipedia**Connected dominating set**— In graph theory, a connected dominated set and a maximum leaf spanning tree are two closely related structures defined on an undirected graph. Contents 1 Definitions 2 Complementarity 3 Algorithms 4 Applic … Wikipedia**Graph coloring**— A proper vertex coloring of the Petersen graph with 3 colors, the minimum number possible. In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called colors to elements of a graph… … Wikipedia