Graph Theory

Question 1

What does κ(G) represent?

Answer 1

minimal vertex cut

Question 2

What does λ(G) represent?

Answer 2

minimal edge cut

Question 3

What does ω(G) represent?

Answer 3

number of components

Question 4

What does δ(v) represent?

Answer 4

degree of v

Question 5

What does |x| represent?

Answer 5

number of “x” – NOT absolute value

Question 6

How many edges are in a complete graph?

Answer 6

n(n-1) / 2

Question 7

What is the sum of the degree of all vertices?

∑v∈v(g) δ(v) = ?

Answer 7

Twice the number of edges. 2*|E(G)|

Question 8

When is a degree sequence graphic?

Answer 8

If there is a corresponding simple graph.

Question 9

If you sum up the contents of a row in an adjacency or incidence matrix, what is the resulting number?

Answer 9

The degree of the vertex. δ(v)

Question 10

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:

Answer 10

isomorphic.

Question 11

Two vertices are connected if:

Answer 11

there is a path between them.

Question 12

A graph is connected if:

Answer 12

all pairs of vertices are connected.

i.e. from any vertex, there is a path to any other vertex.

Question 13

What is a component of G?

Answer 13

A connected subgraph that isn’t strictly contained another connected subgraph of G.

Question 14

What is the difference between a walk and a path?

Answer 14

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.

Question 15

What are vertex/edge cuts?

Answer 15

A subset of the vertices/edges such that if you take them away from the graph, the graph will become disconnected.

Question 16

What can we say about the minimal: vertex cut, edge cut, and degree of vertices in a graph?

Answer 16

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)}

Question 17

What is the minimal vertex/edge cut?

Answer 17

The minimum number of vertices/edges you have to remove to disconnect the graph.

Question 18

What does it mean if a graph is k-connected?

Answer 18

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.

Question 19

If you have two non-adjacent vertices (u,v), the number of vertex independent paths between (u,v) is equal to:

Answer 19

The minimum number of vertices you need to remove to disconnect u and v. (by Mengers Theorem)

Question 20

By Mengers Theorem, the minimum number of vertices you need to remove to disconnect two non-adjacent vertices u and v is equal to:

Answer 20

The number of vertex independent paths between u and v.

Question 21

Which property is “stronger” vertex independence, or edge independence?

Answer 21

Vertex independence. Since vertex independence implies edge independence, but not vice versa.

Question 22

These properties represent what type of graph?

1. V(G)=V1∪V2
2. V1 ∩ V2 = {}
3. E(G)⊆{⟨v1,v2⟩ | v1 ∈V1 and v2 ∈V2}

Additionally, translate each of the above lines into english.

Answer 22

Bipartite graph.

1. The vertex set of G is equal to the union of vertex set V1 and vertex set V2.
2. V1 and V2 have no elements in common. Meaning, V1 and V2 share no vertices.
3. The edge set E(G) contains edges whose endpoints are in different sets.

Question 23

What is a ranked embedding?

Answer 23

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.

Question 24

How does a spring embedding work? (simply)

Answer 24

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.

Question 25

A graph in which no two edges cross is known as what type of graph?

Answer 25

Planar graph.

Question 26

What is Eulers formula?

What does it mean?

Answer 26

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.

Question 27

What is a complete graph?

Answer 27

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.

Question 28

The number of vertices of odd degree in a graph G is:

Answer 28

even.

by the handshaking lemma, a result of the degree sum formula.

Question 29

There exists a strongly connected orientation for a graph iff:

Answer 29

The minimal edge cut is greater than or equal to 2.

λ(G) ≥ 2

Question 30

What does χ′(G) represent?

Answer 30

edge chromatic number

i.e. the minimal k for which G is k-edge colourable.

Question 31

What does χ(G) represent?

Answer 31

vertex chromatic number

i.e. the minimal k for which G is k-vertex colourable.

Question 32

What does ∆(G) represent?

Answer 32

the max degree of G

Question 33

What does it mean if a graph G is k-vertex/edge colourable?

Answer 33

It means the graph can be coloured with k colours, such that no two adjacent vertices/edges have the same colour.

Question 34

How many orientations exist for a simple graph with m edges?

Answer 34

2^m, though, its slightly less if you account for isomorphisms.

Question 35

What does the Four Colours Theorem state?

Answer 35

It is possible to colour any planar graph with 4 colours.

Question 36

What is a closed walk?

Answer 36

A u,v walk where u=v

Question 37

What is a tour?

Answer 37

A closed walk that traverses each edge.

Question 38

What is an Euler Tour?

Answer 38

A tour that traverses each edge exactly once.

Question 39

If a graph G is connected, and all its vertices have even degree, it has a:

Answer 39

Euler tour

Question 40

What is a trail?

Answer 40

A walk that traverses each edge at most once.

Question 41

What is a hamilton cycle?

Answer 41

A cycle containing every vertex exactly once.

If a graph contains a hamilton cycle, it is called Hamiltonian.

Question 42

Diracs theorem says what?

Answer 42

The number of edges is less than or equal to 3n-6