Use this tag for questions in graph theory. Here a graph is a collection of vertices and connecting edges. Use (graphing-functions) instead if your question is about graphing or plotting functions.

learn more… | top users | synonyms

1
vote
5answers
135 views

Does this graph contain $K_5$ or $K_{3,3}$ as subdivision or minor?

Does this graph contain subdivision of $K_5$ or $K_{3,3}$? Does this graph contain $K_5$ or $K_{3,3}$ as minor? I'm not sure if I'm correct, but I think the answer is yes for both questions. $K_5$...
4
votes
3answers
953 views

Can I find the connected components of a graph using matrix operations on the graph's adjacency matrix?

If I have an adjacency matrix for a graph, can I do a series of matrix operations on the adjacency matrix to find the connected components of the graph?
2
votes
1answer
90 views

Factor Group Lemma of Cayley Graph

Factor Group Lemma: Suppose that 1.$N$ is a cyclic, normal subgroup of group $G$. 2.$(s_1,s_2,\ldots,s_m)$ is a hamiltonian cycle in $Cay(G/N;S). 3.The product $s_1s_2\cdots s_m$ generates $N$. ...
1
vote
1answer
81 views

What is the relationship between genus and crossing numbers

I have some questions about topology graph theory and algorithms. Suppose given a graph with genus $k$ ($k\ge1$), if we want to draw this graph on the plane, there are at least $k$ crossing numbers ...
1
vote
1answer
59 views

If the inorder traversal of a binary tree produces ordered output, is the tree a binary search tree?

Given a binary search tree, it's easy to see that the inorder traversal returns values from the underlying set in order (according to the comparator that set up the binary search tree). My question ...
1
vote
1answer
67 views

Found all sets of nodes in a undirected graph that any pair of nodes in that set have a distance larger than N

For a undirected graph $G$, is there a algorithm that found all sets of nodes that satisfies the rule that: in such a set, any pair of nodes have a distance larger than $N$, where $N$ is a positive ...
2
votes
2answers
46 views

The compartment for graph.

Suppose that $G$ is a graph, which is not a clique. Prove that there is a division of the set of vertices $V(G)$ into two subsets $V_1$ and $V_2$ such that $\chi(G)< \chi(G [V1]) + \chi (G [V2])$ ...
3
votes
1answer
62 views

Let $T$ be a tree of order $n \geq 4$, and let $e_1,e_2,e_3 \in E(\overline T)$. Show that $T+e_1+e_2+e_3$ is planar.

Let $T$ be a tree of order $n \geq 4$, and let $e_1,e_2,e_3 \in E(\overline T)$. Show that $T+e_1+e_2+e_3$ is planar. I know that for any tree $m=n-1$ and since $T$ has only one region, it's outer ...
0
votes
1answer
27 views

Graph homomorphism with a non-mapping relation

In [1] it is said that a graph homomorphism is a mapping between two graphs, that is, between their vertices, where the edges are preserved. A mapping is a specific binary relation where any vertex ...
2
votes
1answer
93 views

Find edges part of a simple path between two vertices

Suppose G is an undirected graph. How can I efficiently find all edges in G that are part of a simple path between given vertices A and B?
1
vote
0answers
85 views

Perfect matching in 3-regular graph.

Prove that each vertex 2-connected, 3-regular graph has a perfect matching. Please give some advice. Thanks in advance.
4
votes
1answer
154 views

Trees with odd degree sequence

Define $t(n)$ to be the number of (unlabeled, unrooted) trees on n vertices such that each vertex has odd degree. For example, $t(2) = t(4) = 1$. Every finite nontrivial tree has endpoints and ...
1
vote
1answer
214 views

Euler path in cube [duplicate]

Suppose we have the cube $3\times3\times3$ divided by $1\times1\times1$ cubes. We want to prove that there isn't path from an edge cube to the cube in the center which passes through every cube and ...
4
votes
2answers
605 views

How to determine if a graph has a perfect matching?

I'm practicing for a math challenge and was asked whether the following graph has a perfect matching. I've tried to randomly connect nodes but couldn't find a way to connect the node in such a way ...
2
votes
0answers
54 views

how to count possible planar bipartitions?

i want to find out what small fraction of a solution space a metaheuristic search is actually covering. this case comes down to the number of possible bipartitions for a non-bipartite, undirected ...
3
votes
0answers
105 views

Integer hexagonal grid variations for Harborth

Harborth's conjecture states that every planar graph has a planar drawing in which all edge lengths are integers. I was looking at that, and I wondered what was known about hexagonal grid graphs. For ...
0
votes
1answer
56 views

Why $d(x) + d(y) \le n$ when proving Mantel's theorem

I was going through the Bollobás book on Modern Graph Theory. When proving the Mantel's theorem, that states $n^2/4$ is the lower-bound for having triangles, the proof start from the assumption that: ...
1
vote
0answers
44 views

If I colour $n$ vertices independently, randomly with $n^{(1-x)}$ colours, why is the size of the colour classes $(1+o(1))n^x$?

By $o(1)$, I mean 'little-o' of $1$. A paper I'm reading uses this result, but I can't see where it comes from. Thanks.
17
votes
3answers
473 views

Is it possible to uniquely number faces of a hexagonal grid with consecutive numbers?

You have a grid of regular hexagons. The aim of the game is to have each hex contain the numbers 1-6 on its edges. Each edge must also be connected to another edge that has a value one higher and ...
3
votes
0answers
40 views

Choosing which sets of nodes are 'top' and 'bottom' in bipartite graph representations of real-world complex networks.

A bipartite graph is a triplet $G=(\top, \bot, E)$ where $\top$ is the set of top nodes and $\bot$ is the set of bottom nodes, and $E\subseteq\top\times\bot$ is the set of edges. Often real-world ...
1
vote
0answers
127 views

Comparison with the greedy algorithm

Consider the following algorithm to vertex coloring: First find a maximal independent set of vertices and color these with the color 1. Then find a maximal independent set of vertices in the remaining ...
1
vote
1answer
82 views

Graph Theory Contest Maths

I have never covered Graph Theory so I've been put into a bit of a quandary over how to do these two questions (I am assuming the second is graph theory, if not I will edit it out of the question). ...
-2
votes
3answers
770 views

Graph isomorphism when all vertices have the same degree

Are 2 connected graphs isomorphic if they have the same number of vertices and each vertex has the same degree $k$? I don't know how to prove it but I also can't find a counter example.
0
votes
1answer
70 views

What does $ \chi(Tree)\leq 2 $ mean in graph theory?

I am reading an article about graphs in English. Does $\chi(Tree)\leq 2$ mean that each node has no more then $2$ children?
2
votes
1answer
131 views

Graph theory question about planar graphs

How can i prove that every planar graph can be expressed as a union of five edge-disjoint forests ? I think I should use theorem that says : ' Every planar graph contains vertex with degree 5 or ...
2
votes
2answers
62 views

Graph theory proof about triangles.

Getting a bit stuck on this question: Prove that if any graph $H$ has $\delta (H)> \frac{n}{2}$ then $H$ contains a triangle. ($\delta (H)$ means the smallest degree of a vertex in H) So far I ...
9
votes
1answer
120 views

Are injections harder to find than surjections?

Given two finite sets $A$ and $B$ with $|A|<|B|$ There are more functions from $B$ to $A$ than from $A$ to $B$ except when $|A|=1$ or $|A|=2,|B|=3,4$. See here for proof. It is also true there are ...
0
votes
1answer
132 views

topological graph theory and the first Betti number

I am confused by a statement: in Wikipedia, In topological graph theory the first Betti number of a graph G with n vertices, m edges and k connected components equals $$m - n + k.$$ I am ...
2
votes
1answer
79 views

Geometry and natural numbers

I can't find the solution to the following problem, any help welcome. One is given a natural number N. One has to find N points on a straight line, and a (N+1)th point which is not on this straight ...
0
votes
1answer
88 views

What does the author mean in his proof “It follows by induction hypothesis” in theorem 2.3 in the given article below..

http://www.discuss.wmie.uz.zgora.pl/php/discuss3.php?ip=&url=pdf&nIdA=23384&nIdSesji=-1 What does the author mean in his proof "It follows by induction hypothesis" in theorem 2.3 in the ...
1
vote
0answers
35 views

Expected chromatic number

If $ G = (V, E) $ is an undirected graph where each edge is included with probability $ p \in [0,1] $ is there a way to calculate $\mathbb E[\chi (G)]$ using elementary methods? Or at least establish ...
1
vote
1answer
61 views

Longest path in $n\times n$ grid

Consider an $n\times n$ grid graph. It is easy to construct (self-avoiding) paths in it of length $n(n+2)$, by starting at the upper left corner, going downwards to the lower left corner, going right ...
2
votes
1answer
317 views

Graph Theory: A Tournament Question

First of all, this is a homework question: ...
0
votes
0answers
62 views

Tree-width of a KxK grid

It's well known that the tree-width of a $K\times K$ grid is exactly $K$. However, on the other hand, we know that the tree-width of a chordal graph is the clique number minus 1. The tree-width of a ...
1
vote
1answer
56 views

Path cover in directed graphs

I cannot figure out what this theorem is trying to say: Every directed graph G has a path cover $\mathcal{P}$ and an independent set $\{\mathcal{v}_P | P \in \mathcal{P}\}$ of vertices such ...
0
votes
1answer
37 views

Feasible method of grouping relations

This might be a bad question, I hope not so bad. Problem is I have a set of relations(millions), presumably two arrays hold two nodes(starting, and ending), which together forms a relation(edge). I ...
1
vote
1answer
32 views

Is there a name for this graph density measure?

Let $G=(V,E)$ be an undirected graph. We define the following procedure (randomized greedy coloring): Fix some random ordering over the vertices (each permutation will be chosen w.p. $\frac{1}{|V|...
0
votes
0answers
126 views

Graph Theory: prove the defect version of Hall's theorem

i don't really understand the expression delta(A), and i don't understand how exactly and in what way i am supposed to bound the matching number of G.
1
vote
1answer
74 views

G is a bipartite graph, where for every edge e=(a,b)[a,b are in A,B] d(a)>d(b), and d(a)>0, show that there is a matching saturating A

I think the direction is definitely HALL, i tried using induction on the size of S, where S is some subgroup of A, but i wasn't able to complete the process.
0
votes
1answer
65 views

Showing that a graph doesn't contain a Hamiltonian ccle

In the article here it says that A Hamilton circuit cannot contain a smaller circuit within it. ? What is meant by this? I thought this meant that for example if ...
2
votes
2answers
2k views

Maximum no.of edges in a bipartite graph

I have to prove that for a bipartite graph G on n vertices the number of edges in $G$ is at most $n^2/4$. I used induction on n. induction hypothesis:Suppose for a bipartite graph with less than ...
1
vote
1answer
44 views

MST or not without children ?

I've got an undirected weighted graph G with c:E(G)->IR. Now I want to find a spanning tree, such that a node v arbitrary, shall be an internal node, and among all spanning trees, in which v is only ...
10
votes
2answers
292 views

When is the automorphism group of the Cayley graph of $G$ just $G$?

Let $G$ be a finite group and $S$ a generating set of $G$. We can draw the Cayley graph $C(G,S)$ by putting each element of $G$ as a vertex, and drawing an edge between two elements $g$, $h\in G$ iff $...
4
votes
3answers
327 views

Graph Theory book with lots of Named Graphs/ Graph Families

I'm doing a research about an operation on graphs and I am now in the point where I want to apply it to some named graphs or to some of the graph families like paths, cycles, wheels, etc. I am ...
1
vote
0answers
34 views

Strongly regular directed graph and its complementary graph..

I'm reading a paper (Art Duval) about generalizing the strongly regular idea to directed graphs.. anyway, the lemma is: Also, to be clear, the parameters are: $n$ - number of vertices, $k$ - valency, ...
0
votes
1answer
14 views

If $M=(E,S)$ and $N=(E,F)$ are 2 partition matroids, and $I=S \cap F $ . Is there a matroid with $I$ being its set of independent sets?

If $M=(E,S)$ and $N=(E,F)$ are 2 partition matroids, and $I=S \cap F $ . Is there a matroid with $I$ being its set of independent sets? My intuition says it's correct because $M,N$ are ...
0
votes
1answer
128 views

Examples of transient and recurrent simple random walks on trees

This is a followup to Recurrence or transience of the 1-3 tree in which I discovered that my original guess of an example for some exercises was wrong. (Those exercises can be found in http://pages.iu....
1
vote
1answer
79 views

Is there a name for graphs that only contain cliques?

I'm wondering if there is a name for graphs such that if there is an edge between vertices A and B and a second edge between vertices B and C then there must be an edge between vertices A and C. My ...
2
votes
1answer
59 views

Recurrence or transience of the 1-3 tree

The 1-3 tree is a rooted tree with only the root at level n=1, and from thereafter, $2^n$ vertices at each tier of distance from the root. However, they are not connected as in the binary tree. Put ...
2
votes
2answers
260 views

Finding the shortest cycle in a graph using every edge

Note: this is homework. Please do not give a complete answer. I've had a brief introduction in graph theory. We have been given to find a shortest cycle visiting all edges and starting and finishing ...