Use this tag for questions in graph theory. Here a graph is a collections of vertices and connecting edges. Use (graphing-functions) instead if your question is about graphing or plotting functions.
7
votes
1answer
107 views
Rearrangement of dinner guests
A dinner host wants his guests to move, between main course and dessert, so that everyone gets a complete set of new neighbours.
Guests are seated either side of a long table. Most guests have five ...
4
votes
0answers
93 views
Count number of special onto functions
We define an onto function from $[n] \times [n]$ to $[n-2] \cup \{0\}$ as follows, where $[n] = \{1,2,3,\ldots ,n\}$,
$$f : [n] \times [n] \rightarrow [n-2] \cup \{0\}.$$
1) $f(x,x) = 0$.
2) ...
0
votes
1answer
23 views
Copies of a fixed graph in a random graph
I don't understand why the number of copies of a fixed graph H in a random graph with $n$ vertices and edges chosen with probability $p$ is:
$$\Theta(n^{v(H)}p^{e(H)})$$
1
vote
1answer
50 views
Is this graph coloring problem solved correctly?
On this Wikipedia page about Burnside's lemma, it is calculated that there are 57 rotationally distinct colorings of the faces of a cube with three colors. I'm confused by the way it is done.
They ...
0
votes
1answer
37 views
Can there be a repeated edge in a path?
I was just brushing up on my discrete mathematics specifically graph theory and read the following definition of a walk in a graph
"A walk in a graph is an alternating sequence of vertices and edges ...
2
votes
2answers
43 views
The second largest eigenvalue for Perron-Frobenius matrix
The Perron-Frobenius theorem is about the largest eigenvalue and eigenvector of a non-negative (irreducible) matrix.
My question: Is there any estimation of the difference between the first and ...
1
vote
2answers
54 views
Inequalities between chromatic number and the number of vertices
I am currently doing exercises from graph theory and i came across this one that i can't solve. Could anyone give me some hints how to do it?
Prove that for every graph G of order $n$ these ...
4
votes
3answers
63 views
Points on a sphere
We draw n points, A, B, C, ... Z, on the upper hemisphere of a sphere, and their n antipodal points on the lower hemisphere, a, b, c, ..., z.
We draw the n(n-1)/2 great circles connecting each pair ...
1
vote
0answers
28 views
Topological graphs
Given the universel covering space $\hat{X}$ of $X$ by $p:\hat{X}\rightarrow X$, there exists a bijection between subgroups $H<G=\pi_1(X,x_0)$ and covering spaces $\tilde{X}\rightarrow X$ with ...
0
votes
1answer
22 views
only one central vertex
Let $T$ be a tree and let $m$ be the legnth of the longest path in $T$. Prove that the center of $T$ consists of exactly one point if and only if $m$ is even.
So lets start by doing $\Rightarrow$ ...
1
vote
2answers
37 views
$X(G)=4$ then G contains $K_4$
This is a practice question in my text.
Its a true and false question and I have to prove it its true $X(G)=4$ then G contains $K_4$ where $X(G)$ is the chromatic number. I know this is true but how ...
1
vote
1answer
21 views
Subgraphs of bipartite graphs that contain complete graphs
When is $K_{n}$ a subgraph of $K_{n,n}$?
It looks like from my drawing that for $n=3$ it can't be.
But I don't know how to prove this.
0
votes
1answer
29 views
Cayley's formula question
I need help with wikipedia's explanation for the number of spanning trees in a complete graph.
(http://en.wikipedia.org/wiki/Pr%C3%BCfer_sequence)
Can someone explain the sentence "The proof follows ...
0
votes
0answers
21 views
proof center of a tree
I have questions regarding Proofwiki's proof. (http://www.proofwiki.org/wiki/Tree_has_Center_or_Bicenter)
How can I prove that $\epsilon (x) \ge \epsilon (y)$ in a graph, $\epsilon (x) \ge \epsilon ...
0
votes
0answers
14 views
check my proof on perfect square graph and trees
Prove that no tree with three or more vertices is a perfect square.
(1)the original tree contains at least one pair of vertices such that with $d(x,y)=2$
Suppose the $G$ contained such a pair, say ...
4
votes
1answer
31 views
Nomenclature and notation for some aspects of weighted directed graph.
I'm having some problem with nomenclature some structures and quantities related to weighted directed graph.
Suppose that $A \in \mathbb{R}_+^{N \times N}$ is the weighted adjacency matrix of a ...
1
vote
1answer
53 views
If a graph with $n$ vertices and $n$ edges there must a circle?
How to prove this question? If a graph with $n$ vertices and $n$ edges there must a circle?
1
vote
0answers
36 views
Prove that if 3 planar graphs with same vertices then $G =(V,E_1 \cup E_2 \cup E_3)$ is 18-colorable
Given: $G_1 = (V,E_1), G_2 = (V,E_2), G_3 = (V,E_3)$ three planar graphs on same vertices group $V$. Let $G = (V,E_1 \cup E_2 \cup E_3)$. Prove that $G$ is $18$-colorable.
What I did so far:
...
1
vote
1answer
47 views
Number of nodes in a tree
Suppose I have a tree $T$, which is rooted in some vertex $v$. Assign a number $k$ to $v$ and let $v$ have $k-1$ children, number them accordingly. Go on recursively, i.e. one of the children with ...
1
vote
0answers
18 views
Regularity method: size of $\epsilon$-regular graph parts
I am applying the Regularity method, as described for example here.
I do not understand why the size $l$ of the $k$ resulting sets $V_i$, ie:
$l = |V_1| = |V_2| = ... = |V_k|$
has the following ...
0
votes
1answer
27 views
check my proof on simple walks and circuits
I want to prove that if a graph has no circuits then it is simple.
Consider a walk with a repeated edge, AabBbaC, where A, B, C are strings of vertices.
(Here I reversed the order of edge ba, ...
3
votes
1answer
33 views
distinct edges and vertices (graph theory)
I want to ask about the relationship between distinct vertices and distinct edges.
I was able to come up with an explanation for
"distinct vertices" $\Rightarrow$ "distinct edges".
An edge is ...
1
vote
2answers
34 views
proof of Ore's Theorem
There was a part in Proofwiki's proof that I didn't understand. (http://www.proofwiki.org/wiki/Ore%27s_Theorem)
Although it does not contain a Hamilton cycle, G has to contain a Hamiltonian path ...
0
votes
1answer
22 views
Decomposing flows on a graph as a sum of cycle flows and source flows
I am reading a paper where they say the following is "easy" but I can't seem to see why.
Let $G$ be a finite undirected graph on an edge set $V$ and
let $E$ be its set of oriented edges (i.e. each ...
2
votes
1answer
54 views
What does the notation $[V]^2$ mean (in graph theory)?
In graph theory, a graph is a pair $G=(E,V)$ of sets satisfying $E\subseteq[V]^2$. But what is $[V]^2$?
I suppose that it is the same as $V\times V=V^2$, but I do not know where the square brackets ...
1
vote
1answer
36 views
Let $G$ be the graph whose vertices are binary sequences of length 4, two vertices are adjacent if they have exactly 2 bits different. Is it planar?
Given $G$, a graph whose vertices are binary sequences of length 4. Two vertices are adjacent in $G$ if and only if they differ by exactly two bits. Is it planar?
Here's what I tried to say:
...
1
vote
1answer
29 views
Prove/disprove: In a graph with at least one component that does not contain a hamilton circuit, we can make it hamiltorian by adding a vertex
Prove/disprove: In a graph $G$ with at least one component that does not contain a Hamiltonian circuit, we can add a vertex $x$ and certain edges that connect it with certain vertices in the graph, ...
2
votes
2answers
48 views
trees on six vertices
Show that there are exactly six non-isomorphic trees on six vertices.
("Introduction to Combinatorics" p.183)
The solutions were provided in the book.
But why can we be sure that there are ONLY six ...
2
votes
0answers
18 views
Graph with two copies of $K_{r+1}$ which have $r$ vertices in common
Let $G$ be a graph with $ n > r+1 $ vertices and $t_r(n) + 1$ edges, where $t_r(n)$ is the Turan number i.e. the number of edges of the Turan graph $T_r(n)$. I'm trying to prove the following:
...
0
votes
1answer
33 views
Find a connected bicubic graph with ten vertices that is not Hamiltonian.
I suppose there are know algorithms for this problem, but what are some guidelines I could follow?
I know in a Hamiltonian cycle you can't have "threeways"; how can I make a graph that makes it ...
0
votes
0answers
25 views
using euler circuits for solving mazes
I didn't understand the algorithm explained in my textbook.
("Introduction to combinatorics" P.165)
I would an alternative explanation with an example.
Here is the algorithm:
(i) from a new vertex, ...
0
votes
1answer
25 views
Graph cycles from vertex and degrees
Show that if every vertex in a graph has degree greater than one, then the graph contains a cycle.
Is the converse true?
0
votes
0answers
17 views
Question on proof of Minimality of Prim's Algorithm
Here is the proof that was given in my textbook (P.178 of "Introduction to Combinatorics").
I want to check if my reasoning behind the parts in bold are correct.
Let $T_i$ be the tree obtained by the ...
27
votes
4answers
368 views
How does the divisibility graphs work?
I came across this graphic method for checking divisibility by $7$.
$\hskip1.5in$
Write down a number $n$.
Start at the small white node at the bottom
of the graph. For each digit $d$ in ...
2
votes
1answer
45 views
Graph with no even cycles has each edge in at most one cycle?
As the title says, I am trying to show that if $G$ is a finite simple graph with no even cycles, then each edge is in at most one cycle.
I'm trying to do this by contradiction: let $e$ be an edge of ...
0
votes
0answers
14 views
Smoothing technique for parameter estimation
I have a real-world web-graph and am trying to check the formula
$P = cd^{-\gamma}$, where $d$ is the degree.
I have a problem that there are too many verticies with unique d, so one cannot calculate ...
1
vote
0answers
42 views
How is this kind of subgraph called?
Consider a certain directed graph, G, and one of its subgraphs, S, such that:
S is a strongly connected component of G,
There are no paths from nodes in S to the rest of G,
There is a path from ...
0
votes
1answer
31 views
Check my proof for number of spanning trees?
Let $\tau (G)$ be the number of spanning trees in graph $G$.
I will prove the following claims:
(1) if T is a tree, $\tau (T)=1$
(2) if G is derived from a tree T by replacing one edge of T by a ...
4
votes
1answer
31 views
What is a “maximal” object?
The idea of a "maximal" graph was introduced in a proof for Ore's Condition.
I didn't quite get the idea, and I would like more detailed explanations.
The theorem and proof are as follows.
Suppose G ...
0
votes
0answers
17 views
Proportional-Integral Estimator Question with Agents and Graphs
My question concerns a collection of $n$ agents, with interconnections described by a graph $G = (V,E)$, with Laplacian $L$ and adjacency matrix $A$. The point behind the following dynamical-system is ...
0
votes
2answers
22 views
Proof of the 2 pointer method for finding a linked list loop
The linked list with a loop problem is classical - "how do you detect that a linked list has a loop" ? The "creative" solution to this is to use 2 pointers, one moving at a speed of 1 and the second ...
1
vote
2answers
54 views
Prove that for every planar graph, there is a partition $V = V_1 \cup V_2 \cup V_3$ such that the graphs with those are acyclic
Prove that for every planar graph $G = (V,E)$ with $|V| \geq 3$ there is a partition of V to $V = V_1 \cup V_2 \cup V_3$ such that $V_1 \cap V_2, V_1 \cap V_3, V_2 \cap V_3 = \emptyset$, where for ...
2
votes
0answers
28 views
How many cuts does it take to remove any $n$ vertices from an $m$-dimensional hypercube?
For instance, in $m=3$ dimensions (cube), the following $n=3$ corners (red) can be cut off with a minimum of $C=2$ planes (blue). (Note you are only allowed to cut off the vertices in red.)
So what ...
0
votes
1answer
36 views
determine whether graph is planar
This is not a HW question just a practice exercise in the text.
The question is to determine whether its planar or not. I dont think its Planar and I cant find a subgraph that is homeomorphic to ...
1
vote
1answer
25 views
proof of a tree with two vertices of degree three
This is a practice question from the text.
The Question : Show that a tree with two vertices of degree $3$ must have at least four vertices of degree $1$. I have the answer to PART A.
Part B) Show ...
1
vote
2answers
51 views
number of vertices in a self-complemntary graph
Problem: Prove that the number of vertices of a self-complementary graph must be congruent to 0 or 1 modulo 4.
I think my starting point would be that P4 and C5 are self-complementary and proceed by ...
1
vote
2answers
32 views
Constructing Cubic Graphs of Even Order
The problem is to show how to construct a cubic graph of v vertices whenever v is even. (for v $\ge4$)
I think I'm supposed to use a degree sequence to aid my construction, but I need help getting ...
3
votes
2answers
62 views
Find a manifold which contains embedding of $K_5$
$K_5$ graph is not planar .
I was asked to find a manifold which contains embedding of $K_5$ and use $5$ squares to represent $K_5$ "on" my new manifold.
Embedding means that it can be drawn on the ...
0
votes
0answers
14 views
A book (or tutorial) on probabilistic networks
I use the term "probabilistic networks" to describe graphs for which one or more link lengths are defined as random variables.
Specifically, I'm looking at optimization problems on these graphs. An ...
4
votes
1answer
48 views
Characterisation of linearly separable points of a hypercube
Essentially, linearly separable points are just those corners that can be cut off with just one slice as marked out by a hyperplane.
E.g. for a cube, the following 4 points (red) are not linearly ...
