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

2
votes
1answer
26 views

Every trail can be extended to an Euler tour

Let G be a nontrivial and eulerian graph, and let $v \in V(G)$. Prove that every trail of $G$ with origin $v$ can be extended to an Euler tour of $G$ if and only if $G - v$ is a forest. I've ...
1
vote
1answer
25 views

How to show that a graph is not hamiltonian

How can i prove that a graph that has 1 vertex adjacent with 3 other vertexes that have 2 neighbours each is not a hamiltonian graph ? Any help would be apreciated.
1
vote
0answers
12 views

Does a Matroid's graph not having 3-separation mean its dual doesn't have 3-separation?

Let there be a graph $G$, with a matroid $M(G)$. If there is no 3-separation in $M$, does it imply there isn't one in $M^*$? Any hints would be much appriciated!
1
vote
5answers
91 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. ...
2
votes
3answers
61 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
34 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
27 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
28 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
61 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
40 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])$ ...
0
votes
0answers
11 views

Finding the neighbors of a node/vertex in a 2D mesh

I have a 2D mesh defined by nodes and elements. Structure of a node: Node ID, X position, Y position Structure of an element: Element ID, Node 1, Node 2, Node 3, Node 4 Example of a 2x2 elements ...
3
votes
1answer
48 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
20 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 ...
0
votes
0answers
14 views

Extremal eigenvalues & eigenvectors of skew-adjacency matrix

I am looking for ways to obtain the extremal eigenvalues and eigenvectors of the skew-adjacency matrix of a directed graph. The graphs I am interested in are not regular (but they have a maximum ...
2
votes
1answer
49 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
votes
2answers
22 views

Algorithm for diffrent verticles [closed]

Suppose we have a graph and we want all his edges to have different amount of verticles.Is there an algorithm(not multigraph).For 2 edges there is exactly one verticle
0
votes
0answers
16 views

Connection between Directed Acyclic Graphs and Boolean Functions

I am given a set of $n$ vertices and testing some properties over the set of all directed graphs over them (i.e. acyclicity and bipolarity). I already done this by generating every undirected graph ...
1
vote
0answers
38 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.
3
votes
1answer
63 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
36 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 ...
0
votes
0answers
34 views

Memory efficient algorithm to find network diameter

I am trying to implement memory efficient algorithm to find network diameter. So far I have classic bfs but it fills memory for large graphs (I am trying to work with Orkut data set) The ...
4
votes
2answers
170 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
33 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 ...
2
votes
0answers
28 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
25 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: ...
0
votes
0answers
30 views

Prove graph is a tree

Prove: Graph is a tree if and only if every pair of two distinct vertices are joined by only one path, and the vertices of this path are all distinct. I can easily see on a diagram that this is ...
0
votes
0answers
19 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.
15
votes
3answers
316 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 ...
1
vote
0answers
14 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
27 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 ...
0
votes
0answers
34 views

Hall theorem, task.

Let $F$ be a family consisting of $m$ non-empty subsets of $E$, and let $A$ be a subset of $E$. By applying Hall's theorem to the family consisting of $F$ together with $|E| - m$ copies of $E - A$, ...
1
vote
1answer
47 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
38 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
45 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
72 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
47 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
101 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
35 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
42 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
46 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
22 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
28 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
189 views

Graph Theory: A Tournament Question

First of all, this is a homework question: ...
0
votes
0answers
19 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
0answers
25 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
20 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
20 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. ...
0
votes
0answers
36 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.
0
votes
1answer
25 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
29 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 ...