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
127 views

Graph of unbounded degree?

I was reading about The Graph Isomorphism Problem on Wikipedia and the article lists a number of special cases for which the problem can be solved in polynomial time. One of these cases is a graph of ...
0
votes
1answer
79 views

Minimum no of colors needed to color a rectangular area with unit cells so that adjacent cells do not have the same color(with wrapping)?

Given a rectangular m x n plane with unit cells(total m.n cells), what is the minimum no. of colors required to fill the cells so that no two adjacent cells have the same color? In the normal case(no ...
1
vote
1answer
206 views

Explicit formula for exponential objects in category of digraphs

I have already asked a similar question: Exponential object in a category of graphs but earlier I have asked only about existence of exponential object, while in this question I ask for exact formulas ...
0
votes
1answer
87 views

Euler circuit, Hamilton cycle

Is there any graph $G$ with $\kappa(G) < \lambda(G) < \delta(G)$? Is there a graph which has a Euler circuit but no Hamilton Cycle? $\kappa(G)$ is the vertex connectivity, $\lambda(G)$ is the ...
0
votes
0answers
95 views

Graph theory based on k-connected graph on Menger's Theorem

We have a $K$-connected graph. This graph has non empty disjoint subsets $S_1$ and $S_2$ of $V(G)$. How to show that there exist $k$ internally disjoint paths $P_1, P_2, \ldots, P_K$ such that each ...
1
vote
2answers
50 views

Quantity of an object after proliferation

A small creature called "Charza" lives in blocks of an infinite square. An infinite number of them can live in a block. After one hour , one Charza is divided into 4 Charzas and each one moves into ...
1
vote
0answers
78 views

Complete tripartite graph hamiltonian

Let $G_{a,b,c}$ be a complete tripartite graph. For what values of $a, b$ and $c$ is $G_{a,b,c}$ Hamiltonian?
2
votes
1answer
208 views

Finding number of spanning trees

I understand how the deletion-contraction recurrence works, but I don't get how they managed to deduce the number of spanning trees for the graphs in the 4th row.
0
votes
1answer
74 views

Non-Isomorph trees of a graph

Please consider this graph How many non-Isomorph trees with 4 vertex has this graph? Is there any formula that show number of non-Isomorph trees with $n$ vertices? thanks
0
votes
2answers
69 views

Caley graphs of gruops and symmetric generating sets

There are several examples (of which Wikipedia show at least one) when the Caley graph (G,U) of a group G (where U generates the group) depend on the choice of generating set. Is requiring that the ...
0
votes
1answer
77 views

If the number of edges in a spanning forest is $n-k$, then it has $k$ components.

The following proposition about the number of components in a spanning forest of a graph $G$ has an easy inductive proof. You are asked to provide it in the exercises. Proposition 12.1. Let ...
1
vote
1answer
111 views

Non-isomorphic simple graphs: order $n$, size $\displaystyle \frac{na}{2}$, degree sequence $(a,a,a,…,a) \in \mathbb{N}^n$

If a simple graph has order $n$, size $\displaystyle \frac{na}{2}$ and degree sequence $(a,a,a,...,a) \in \mathbb{N}^n$ then is it unique up to isomorphism? I thought of this question while ...
10
votes
1answer
242 views

From matrices to bipartite graphs

Assume $G(A,B)$ is a bipartite graph and assume $L(G)$ is the adjacency matrix of its line graph. define $$B=[3\text{I}+L(G)]^{-1}$$. Is it always the case that for each edge $e=(a,b)\in G$, we have: ...
1
vote
1answer
126 views

Another condition for bipartite graphs

Let $G$ be a graph. Then prove $G$ is bipartite if and only if for all subgraphs $H$ of $G$ with no isolated vertices. $\alpha(H)=\beta'(H)$. Here $\alpha(H)$ is the size of the largest independent ...
0
votes
2answers
164 views

Possibility of an Eulerian Path or Cycle.

Suppose that a connected graph G has 11 vertices and 53 edges. Show that G is not Eulerian. I can prove it for a simple graph by saying that the sum of degrees of all vertices can be maximum 100 (max ...
1
vote
0answers
46 views

Subgraph without “holes”

does everyone know, if there already exists a definition of subgraphs, which do not contain a "hole"? EDITED: That means: I presuppose a planar embedding of a graph G and I want to find a connected ...
1
vote
1answer
37 views

Number of points that allow a topological space to stay connected

This question stems from a problem a friend of mine in the software field posed with regards to a graph. I am curious as to whether there is some analogue for topological spaces in general , maybe ...
2
votes
2answers
45 views

What are multiple isomorphisms?

For example, this graph has "multiple isomorphisms." What does that mean? And could you list them? I don't understand how there can be more than one.
0
votes
1answer
173 views

Distribution of connected components in a Random Graph with fixed number of edges

Given $N$ vertices, I am interested in the distribution of the size of connected components of the random graph formed by assigning $M$ edges to randomly chosen pairs of vertices so as to form a ...
0
votes
0answers
118 views

Applet to find least-crossings drawing for an input graph

Is there a convenient online applet that allows me to draw a graph, after which it outputs a plane drawing of an isomorphic graph that has (approximately) the least number of crossings among all ...
0
votes
1answer
485 views

Graph Theory: How do we know Hamiltonian Path exists in graph where every vertex has degree ≥3?

I am trying to prove that if every node of a graph G has degree of at least 3 then G contains a cycle and a chord. My current approach is as follows: Separate the graph G into connected components ...
1
vote
3answers
711 views

Pigeonhole Principle Question - Group of 6 people, do 3 either know each other or not?

Prove that in any group of 6 people there are always at least 3 people who either all know one-another or all are strangers to one-another. Hint: Use the pigeonhole principle. I don't see how this ...
0
votes
1answer
128 views

In a party with 2000 persons, determine # of people who know everyone

In a party with 2000 persons, among any set of four there is at least one person who knows each of the other three. There are three people who are not mutually acquainted with each other. How many ...
1
vote
1answer
61 views

Constraints on sets of RPG skill bonuses as a graph problem

A friend of mine is creating a tabletop roleplaying game and asked for my help with a particular problem. I wrote a quick and dirty solution, but am now intrigued by what math would underlie a more ...
2
votes
1answer
107 views

The automprphism group of the complete binary rooted tree height 3

Can someone give me some help with this problem: How do I find the automorphism gruop of the complete binary rooted tree height 3 (15 vertices)? when an automorphism F on a graph G=(V,E) is defined ...
1
vote
1answer
59 views

Contractibility of topological spaces associated to posets

Suppose $\mathcal{P}$ is a partially ordered set. To $\mathcal{P}$ we can associate a simplicial complex $K(\mathcal{P})$ whose $n$-simplices are the chains of length $n+1$ in $\mathcal{P}$. Since ...
5
votes
2answers
85 views

Do I influence myself more than my neighbors?

Consider relations between people is defined by a weighted symmetric undirected graph $W$, and $w_{ij}$ shows amount of weight $i$ has for $j$. Assume all weights are non-negative and less than $1$ ...
2
votes
0answers
31 views

Graphs whose minimal disconnecting sets have the same cardinality

Given a graph $G$, is there a nice characterization of graphs whose minimal (w.r.t. set inclusion) disconnecting sets† all have the same cardinality $\lambda$? If we call this property $P_\lambda$, ...
0
votes
1answer
61 views

Matching Graph Drawing

How could I draw a graph that is connected, 3-regular that has both a cut vertex and a perfect matching? I know every simple 3-regular graph with no cut-edge has a perfect matching, but not sure how ...
0
votes
2answers
48 views

Explain why the following collection of sets does not have a system of distinct representatives

Need help with this. Explain why the following collection of sets does not have a system of distinct representatives: A: {5, 7} B: {1, 2, 3, 4, 5} C: {4, 5} D: {6, 7} E: {4, 7} F: {1, 2, 3, 4, 6, 7} ...
2
votes
1answer
1k views

Painting a cube with 3 colors (each used for 2 faces).

A cube is about to get fully painted using $3$ different colors. Each color is being used for $2$ faces of a cube. How many different cubes can be created this way? I saw this in a fifth ...
1
vote
2answers
48 views

Is this graph a graceful tree?

Suppose we have a graph $G=(V,E)$ where $V=\{0,1,\ldots,n\}$ and $E$ consists of $n$ edges in such a way that the set of absolute differences $\{|i-j||ij\in E\}$ is exactly the set $\{1,\ldots,n\}$. ...
0
votes
1answer
65 views

Distance Metric in 4 dimensions $\Bbb R^3\times SO(2)$

The euclidean distance metric, $\sqrt{dx^2+dy^2+dz^2}$, shows the shortest distance between two points in $\Bbb R^3$. What would be the distance metric to show the shortest distance between two ...
1
vote
1answer
65 views

Graph walking: smallest set of “blocking” nodes

I'm not sure I've got the terminology right in my question, but here's conceptually what I'm looking for. In a directed acyclic graph with a single root node and multiple end nodes, how can I can ...
0
votes
1answer
54 views

If $|V(G)|=n$ and $e(G)>\frac{n}{4}\{1+\sqrt{4n-3}\}$ then $G$ contains 4-cycle

This question is linked to my former question Special properties of subgraphs I want to practice this technique a little bit more and want to show that if $|V(G)|=n$ and ...
1
vote
1answer
71 views

Solving a Gaussian elimination problem.

I have been given a graph with n nodes. Now, I have to color every node of this graph by k colors, number from 0 to k-1. Now, there is a rule. For a node $x$ with adjacent nodes $y_1 , y_2, y_3, ...
0
votes
1answer
106 views

Depth of BFS Tree With Different Root Nodes

I need to either prove or disprove that for any node of a graph, the depth of the BFS tree using this node as root is always the same. My intuition is that this is true, but I'm having difficulty ...
0
votes
1answer
87 views

Convergence of $\text{ex} (n;P)/ \binom n2$ for Petersen graph

This question is linked to For a graph $G$, why should one expect the ratio $\text{ex} (n;G)/ \binom n2$ to converge? where an argument was given that this specific ratio converges for ...
1
vote
2answers
94 views

Special properties of subgraphs

I have two statements I am not sure how to prove them: (1) Every graph with $n=|V(G)|\ge 6$ and size $\lfloor n^2/4\rfloor+1$ contains a 5-cycle $C_5$ (2) Every graph with $n=|V(G)|\ge 5$ and size ...
0
votes
1answer
47 views

Maximal graph that does not contain Hamiltonian cycle

My lecture notes in Graph Theory states that a graph of order $n$ and with size (= number of edges) $\binom n 2-(n-2)$ is the maximal graph that does not contain a Hamiltonian cycle. My question now ...
1
vote
0answers
124 views

Are there necessary and sufficient conditions of a graph to decompose into two Hamiltonian cycles?

Let $G$ be a graph. Definition: $G$ is decomposable into two Hamiltonian cycles if the edge set $E(G)$ can be partitioned into two disjoint Hamiltonian cycles. Obviously, if $G$ is decomposable into ...
3
votes
2answers
196 views

puzzle on parks

A park contains paths that intersect at various places. The intersections all have the properties that they are 3-way intersections and that, with one exception, they are indistinguishable from each ...
2
votes
0answers
46 views

Filling a infinite colored graph with basis

This is a mathematical question raised from engineering and physics: Is there some established mathematical approach in filling a physical lattice with some colored basis (black and white here)? For ...
2
votes
0answers
58 views

Adajcency matrix of Kneser Graph

What is the structure of adjacency matrix of Kneser graphs $K(n,k)$? Do they have any nice structure?
0
votes
1answer
49 views

Need help with this question. A graph has K10 as a subgraph. What does this tell us about the size of a maximum matching?

Need help with this question. A graph has K10 as a subgraph. What does this tell us about the size of a maximum matching? (Does it give us an upper bound? A lower bound? Or does it tell us nothing?)
2
votes
1answer
154 views

Monotonically increasing path in a complete graph

Given a complete graph with n vertices such that all edge weights are distinct. Prove that we can find a monotonically increasing path of length n-1. I tried finding such a path by sorting the edges ...
0
votes
1answer
129 views

Proof for hamiltonian cycle in grids having even no. of nodes

How can I go about proving that an undirected graph having even no. of nodes (at least one of the rows or columns are even - excluding line graphs of course) have a hamiltonian cycle? I have managed ...
1
vote
0answers
56 views

Prove that a finite complete graph can be embedded in $\mathbb{R}^3$

I've actually found a few intuitive examples where edges are taken to a twisted cubic and and the vertices are arranged in a certain way and that's very nice, but I'm actually more interested in a ...
2
votes
1answer
65 views

connectivity and graph construction

this might be very stupid question for regular maths students, but I had the following thought after reading about $2$ connected graphs, and thought about asking it. Now $G$ is $2$ connected is ...
0
votes
1answer
566 views

counting cycles in an undirected graph

here is the problem: http://oi39.tinypic.com/30lkpvp.jpg this is the solution: http://oi41.tinypic.com/14wgleo.jpg my question is this. how did they know that it has edges between all ${n \choose ...