Graph Theory Flashcards
What does κ(G) represent?
minimal vertex cut
What does λ(G) represent?
minimal edge cut
What does ω(G) represent?
number of components
What does δ(v) represent?
degree of v
What does |x| represent?
number of “x” – NOT absolute value
How many edges are in a complete graph?
n(n-1) / 2
What is the sum of the degree of all vertices?
∑v∈v(g) δ(v) = ?
Twice the number of edges. 2*|E(G)|
When is a degree sequence graphic?
If there is a corresponding simple graph.
If you sum up the contents of a row in an adjacency or incidence matrix, what is the resulting number?
The degree of the vertex. δ(v)
If each vertex in a graph G1 is associated with a vertex in a graph G2 such that the edges correspond, we can say G1 and G2 are:
isomorphic.
Two vertices are connected if:
there is a path between them.
A graph is connected if:
all pairs of vertices are connected.
i.e. from any vertex, there is a path to any other vertex.
What is a component of G?
A connected subgraph that isn’t strictly contained another connected subgraph of G.
What is the difference between a walk and a path?
A walk is just a sequence of vertices and edges.
In a path, all vertices the vertices are unique.
i.e. you never cross the same vertex twice.
What are vertex/edge cuts?
A subset of the vertices/edges such that if you take them away from the graph, the graph will become disconnected.
What can we say about the minimal: vertex cut, edge cut, and degree of vertices in a graph?
The minimal vertex cut is less than or equal to the minimal edge cut which is less than or equal to the minimal degree of the vertices in a graph.
κ(G) ≤ λ(G) ≤ min v∈V(G) {δ(v)}
What is the minimal vertex/edge cut?
The minimum number of vertices/edges you have to remove to disconnect the graph.
What does it mean if a graph is k-connected?
that the minimal vertex cut is greater than or equal to k.
κ(G) ≥ k
i.e. it has more than k vertices and remains connected whenever fewer than k vertices are removed. You have to remove k+ vertices to disconnect the graph.
If you have two non-adjacent vertices (u,v), the number of vertex independent paths between (u,v) is equal to:
The minimum number of vertices you need to remove to disconnect u and v. (by Mengers Theorem)
By Mengers Theorem, the minimum number of vertices you need to remove to disconnect two non-adjacent vertices u and v is equal to:
The number of vertex independent paths between u and v.
Which property is “stronger” vertex independence, or edge independence?
Vertex independence. Since vertex independence implies edge independence, but not vice versa.
These properties represent what type of graph?
- V(G)=V1∪V2
- V1 ∩ V2 = {}
- E(G)⊆{⟨v1,v2⟩ | v1 ∈V1 and v2 ∈V2}
Additionally, translate each of the above lines into english.
Bipartite graph.
- The vertex set of G is equal to the union of vertex set V1 and vertex set V2.
- V1 and V2 have no elements in common. Meaning, V1 and V2 share no vertices.
- The edge set E(G) contains edges whose endpoints are in different sets.
What is a ranked embedding?
A type of graph embedding that can be performed on bipartite graphs such that each “row” of the embedding contains vertices from a different set.
How does a spring embedding work? (simply)
A spring embedding is constructed by assigning attractive forces to adjacent vertices, and repelling forces to non-adjacent vertices. Calculations are then performed until an equilibrium is achieved, and then you’ll have the result of the embedding.
A graph in which no two edges cross is known as what type of graph?
Planar graph.
What is Eulers formula?
What does it mean?
n-m+r = 2
In a planar graph, it means that the number of vertices, minus the number of edges, plus the number of regions, is equal to 2.
What is a complete graph?
A complete graph is a graph in which every node is directly connected to every other node. In a graph with N vertices, each node will have a degree of n-1.
The number of vertices of odd degree in a graph G is:
even.
by the handshaking lemma, a result of the degree sum formula.
There exists a strongly connected orientation for a graph iff:
The minimal edge cut is greater than or equal to 2.
λ(G) ≥ 2
What does χ′(G) represent?
edge chromatic number
i.e. the minimal k for which G is k-edge colourable.
What does χ(G) represent?
vertex chromatic number
i.e. the minimal k for which G is k-vertex colourable.
What does ∆(G) represent?
the max degree of G
What does it mean if a graph G is k-vertex/edge colourable?
It means the graph can be coloured with k colours, such that no two adjacent vertices/edges have the same colour.
How many orientations exist for a simple graph with m edges?
2^m, though, its slightly less if you account for isomorphisms.
What does the Four Colours Theorem state?
It is possible to colour any planar graph with 4 colours.
What is a closed walk?
A u,v walk where u=v
What is a tour?
A closed walk that traverses each edge.
What is an Euler Tour?
A tour that traverses each edge exactly once.
If a graph G is connected, and all its vertices have even degree, it has a:
Euler tour
What is a trail?
A walk that traverses each edge at most once.
What is a hamilton cycle?
A cycle containing every vertex exactly once.
If a graph contains a hamilton cycle, it is called Hamiltonian.
Diracs theorem says what?
The number of edges is less than or equal to 3n-6
