Middle East Technical University Fall 2001 Math 341 Graph Theory

MIDTERM I, PART I

NOVEMBER 3, TIME: 40 MIN

Name, ID, signature: ——————————————————————————————————– Mark the correct statements (there may be more then one correct answer

in each problem)

A graph is

(1) a subset of the plane or of the space

(2) a set of vertices and a set of edges

(3) an ordered set of vertices and a set of edges

(4) a union of the vertices and the edges

(5) a set of vertices, a set of edges and a set of faces ——————————————————————————————————–

A trivial graph is a graph which

(1) contains no edges

(2) contains no vertices and no edges

(3) contains only one vertex

(4) contains only one edge ——————————————————————————————————–

An edge in a graph is

(1) a pair of vertices

(2) an ordered pair of vertices

(3) a curve on the plane connecting a pair of vertices

(4) is well-defined only for a graph diagram, not for a graph ——————————————————————————————————–

The set of vertices in a graph

(1) is always an ordered set

(2) can be any non-empty subset of a plane

(3) can be any non-empty set

(4) can be an empty set

(5) is always a finite set ——————————————————————————————————–

A plane graph diagram of a graph G is

(1) a planar graph isomorphic to G

(2) a geometrical presentation (image) of a graph G in a plane

(3) is unique (up to topological isomorphism)

(4) cannot be defined if G is a pseudo-graph ——————————————————————————————————–

Typeset by AMS-TEX

An edge in a graph diagram

(1) is a pair of vertices

(2) is an arc (curve) connecting a pair of vertices

(3) cannot pass through more then 2 vertices

(4) cannot intersect any other edge of this diagram (except at a vertex)

(5) can intersect any other edge of this diagram, if it is not a plane graph

diagram ——————————————————————————————————–

A pseudo-graph

(1) is a graph diagram

(2) must contain loops

(3) must contain multiple edges

(4) can contain either loops or multiple edges

(5) may contain oriented edges

(6) must be disconnected

(7) is dual to a plane graph

(8) can be dual to a plane graph ——————————————————————————————————–

A face of a graph

(1) is a subset of a plane or another surface

(2) is a set of vertices

(3) is a set of edges

(4) can be defined only for a graph diagram on a surface ——————————————————————————————————–

A subgraph of G

(1) contains all vertices of G and some of its edges

(2) contains some vertices and some edges of G

(3) contains some vertices of G and edges which are possibly not edges of G (4) is a subset of a graph diagram of G

(5) cannot be a pseudo-graph, if G is a graph ——————————————————————————————————–

A path in a graph is

(1) a sequence of vertices

(2) a sequence of edges

(3) a sequence of directed edges

(4) a set of edges

(5) is defined actually only for graph diagrams, not graphs themselves

(6) a subset of the plane

(7) a piecewise-smooth curve on the plane ——————————————————————————————————–

A cycle in a graph G

(1) bounds always a face

(2) must have pairwise incident edges

(3) must have consecutively incident edges

(4) must have the first and the last edges incident

(5) is formed by vertices, which are cyclically incident ——————————————————————————————————– A connected component of a graph G is

(1) any connected subgraph of G

(2) a minimal spanning subgraph of G

(3) a maximal connected subgraph of G

(4) not always a subgraph of G

(5) well defined actually only for a graph diagram of G, not G itself

(6) well-defined only for a planar graph G ——————————————————————————————————–

The degrees of all the vertices of a graph G are ⩾ 3 if G is

(1) any bipartite graph

(2) any cubic graph

(3) any complete graph

(4) the skeleton of any convex polyhedron

(5) any planar graph ——————————————————————————————————–

An Eulerian graph

(1) cannot be a pseudo-graph

(2) must have all vertices of even degree

(3) may have exactly one vertex of odd degree

(4) may have exactly two vertices of odd degree ——————————————————————————————————–

An Eulerian graph

(1) is not actually a graph, but a graph diagram

(2) cannot be a tree

(3) cannot be a tree with more then two leaves

(4) is always a planar graph

(5) cannot be a cubic graph

(6) is always a bipartite graph ——————————————————————————————————–

A bipartite graph

(1) cannot be a pseudo-graph

(2) cannot be a tree

(3) is always a tree

(4) is always 2-colorable

(5) is always 3-colorable

(6) is a cubic graph

(7) is always connected

(8) is always a planar graph ——————————————————————————————————–

A graph G is 4-colorable if we can color in 4 colors

(1) its vertices

(2) its edges

(3) its faces ——————————————————————————————————– A tree

(1) does not contain cycles

(2) is any connected graph with the number of vertices bigger by 1 then the number of edges

(3) is always connected

(4) has always a vertex called the root

(5) contains always at least two leaves (unless it is trivial)

(6) always contains more then two leaves (if it is non-trivial)

(7) can never be a cubic graph

(8) is not necessarily a planar graph

(9) may be a pseudo-graph ——————————————————————————————————–

A spanning tree of a connected graph G

(1) always exist if G is connected

(2) is unique if G is connected

(3) is unique up to isomorphism if G is connected

(4) is a maximal subtree of G

(5) is a minimal spanning subgraph of G

(6) is a spanning subgraph of G not containing cycles

(7) must coincide with G if G is a tree ——————————————————————————————————–

A forest

(1) cannot have more edges then vertices

(2) is always planar

(3) may have isolated points

(4) cannot have a pair topologically non-isomorphic diagrams in the plane ——————————————————————————————————–

The tree-order is defined

(1) on the vertices of a tree

(2) on the edges of a tree

(3) on the vertices of a rooted tree

(4) on the edges of a forest

(5) it is defined only for special rooted trees ——————————————————————————————————–

The complementary graph for a graph G

(1) have the same set of vertices as G

(2) have the complementary set of vertices

(3) have no common edges with G

(4) have the same set of edges as G

(5) cannot be isomorphic to G

(6) is always isomorphic to G

(7) is not a graph, but a graph diagram

(8) depends on the choice of a graph diagram for G ——————————————————————————————————– The dual graph for G

(1) is the same as the complementary graph

(2) is defined for a graph diagram of G, rather then for graph G itself

(3) have the same number of vertices as G

(4) have the same set of vertices as G

(5) have the same number of edges as G

(6) have the same set of edges as G ——————————————————————————————————–

The Euler formula v − e + f = χ(F) for graphs on a surface F is valid

(1) only for orientable surfaces F

(2) only if the faces are simply connected

(3) only if the graph is connected

(4) only if the graph is a skeleton of a convex polyhedron ——————————————————————————————————–

Examples of oriented surfaces are

(1) a plane

(2) a sphere

(3) a projective plane

(4) a torus

(5) a Klein bottle

(6) a sphere with handles ——————————————————————————————————–

The Ramsey number r(p, q) is

(1) the number of edges in a subgraph of K_{p} not containing \overline{K}_{q}

(2) the number of non-isomorphic spanning trees in Kp, q

(3) the minimal number of vertices in a graph G containing neither K_{p} nor \overline{K}_{q} as a subgraph

(4) the minimal number of edges in a graph G containing neither K_{p} nor \overline{K}_{q} as a subgraph

(5) the minimal number of edges in a subgraph of K_{p} not containing \overline{K}_{q} as a

subgraph ——————————————————————————————————–

An isomorphism between graphs G and F is 1-1 correspondence between

(1) the vertex sets of G and F, preserving adjacency of the vertices

(2) the sets of edges of G and F, preserving adjacency of the edges

(3) both the vertex sets and the sets of edges of G and F, so that adjacency

between the corresponding edges and vertices is preserved ——————————————————————————————————–

The number of edges in K_{4,5} is

(1) 9

(2) 10

(3) 12

(4) 20

(5) 25

(6) 30 ——————————————————————————————————– The number of edges in K_{6} is

(1) 15

(2) 18

(3) 25

(4) 30

(5) 36 ——————————————————————————————————–

The number of edges in \overline{K}_{3,4} is

(1) 9

(2) 10

(3) 12

(4) 16

(5) 21

(6) 25 ——————————————————————————————————–