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
2answers
396 views

Graph Theory mixed with probability - hard question

Suppose we wish to construct a graph in the following manner: Denote the vertices of the graph as $1,2,\dots,n$. For every pair $\{i,j\}$, we flip a fair coin. If it comes up tails, $\{i,j\}$ is an ...
1
vote
1answer
86 views

Proof related to breadth first search

Suppose a connected graph G has a cycle C of length n. Prove that in any breadth-first search tree of G, any two vertices in C are at most $\lfloor\frac{n}{2}\rfloor$ levels apart. No idea how to ...
0
votes
2answers
918 views

How to determine whether the pair of graphs is Graphs Isomorphic

If two graphs $G_i$ and $G_j$ are isomorphic, please provide a bijection from the vertex set of $G_i$ to $G_j$, if the two graphs are not isomorphic, please provide a structural difference graphs ...
6
votes
1answer
373 views

What is graph theory interpretation of this linear programming problem?

So, I am looking at a paper by Rosenfeld, "On a problem of C.E. Shannon in graph theory", where he gives necessary and sufficient conditions for a graph $H$ to satisfy $$\alpha(G \boxtimes H) = ...
0
votes
1answer
305 views

Hamiltonian & Eulerian paths, one vertex graph

Does the graph with only one vertex have an Eulerian path? And, does it have a Hamiltonian path?
1
vote
2answers
357 views

Breadth first search tree's cycles [duplicate]

Possible Duplicate: Proof related to breadth first search I'm trying to prove the following: Suppose a connected graph $G$ has a cycle $C$ of length $n$. Prove that in any breadth-first ...
1
vote
1answer
324 views

Hint on proving this inequality for a planar graph?

Let $G$ be a connected planar graph with $p$ vertices, where $p \geq 3$. Let $t$ denote the number of vertices in $G$ with degree less than $6$. Prove that if $G$ has no cycles then $t \geq ...
4
votes
1answer
75 views

A group and an associated digraph

I am trying to understand the proof of the following statement: Let $\Gamma=\{g_1,\cdots,g_n\}$ be a group. Define a digraph $G$ by joining $g_i$ to $g_j$ by an edge of color $k$ if ...
2
votes
3answers
442 views

Multipartite graphs which are not planar

Please take a look at these definitions: A multipartite graph is a graph of the form $K_{r_1,\ldots, r_n}$ where $n > 1$, $r_1, \ldots, r_n\ge 1$, such that The set of nodes of the ...
0
votes
1answer
58 views

Related to Hall's Theorem

I do not understand the emphasized inequality: http://s11.postimage.org/gnnf1yirn/Capture.png How is it that if the size of X is greater than n, then the number of its neighbours is greater or equal ...
5
votes
2answers
358 views

Suppose there are two different spanning trees for a simple graph. Must they have an edge in common?

My instinct is yes, but I don't know how to formalize it into a proof. I still haven't wrapped my head around spanning trees yet. Any thoughts are appreciated!
2
votes
1answer
469 views

The number of connected components of a $k$-regular graph equals the multiplicity of k

In similar vein to this question, I am trying to understand the proof of the fact that in a $k$-regular graph, the multiplicity of the eigenvalue $k$ equals the number of connected components. The ...
1
vote
0answers
42 views

Normalized Cuts and Spectra

I'm looking for a fleshed out proof of the following theorem. Theorem: Let $G=(V,\mathbf{W})$ be an undirected, edge-weighted graph with normalized Laplacian $\mathbf{L}_N$. Furthermore, let ...
3
votes
1answer
307 views

probabilities in Random Graphs

I am trying to find the probability of a bernoulli random graph on $n=10$ vertices with probability that an edge connects any pair of vertices is $p=\frac{1}{6}$ as $n\to \infty$. This is what I ...
6
votes
2answers
533 views

Planar graphs & Spanning trees

Does there exist a planar graph whose edges can be coloured either red, green or blue in such a way that the red edges form a spanning tree, the green edges form a spanning tree, and the blue edges ...
3
votes
1answer
134 views

Number of squares in a hypercube

I am trying to count the number of $4$-cycles in the hypercube $Q_n$. Clearly if $x,y$ are two distinct vertices with two common neighbors then we get a $4$-cycle. But how do I count such $x$ and $y$? ...
0
votes
1answer
142 views

Planar graph with all drawing topologically isomorphic , but whose planar embending are not equivalent

I have to find an exemple on a 2-connected planar graph whose drawing are all topologically isomorphic but its planar embeddings are not equivalent. I thought to use an cycle and some overturning to ...
1
vote
0answers
29 views

Plane graph combinatorially isomorphic to one with all edges straight

I have this problem. I have to show that every plane graph is combinatorially isomorphic to a plane graph whose edges are all straight. I Also have an hint that says to give a plane triangulation and ...
0
votes
1answer
362 views

Adjacency matrices needed for common graphs

I'm making a program which requires adjacency matrices of undirected graphs. In particular, I'd like the adjacency matrices for the graphs in this wiki link: ...
-1
votes
1answer
565 views

Hamiltonian Cycles and minimum vertex degrees

Take a graph $G$ on $n\ge 4$ vertices and suppose that every vertex has degree at least $\frac12n$. Does $G$ necessarily contain a Hamiltonian cycle? (Either give a proof or provide a ...
0
votes
1answer
554 views

How to find the maximum number of vertices in a tree with respect to maximum path length and maximum degree value

Given a tree, find the maximum number of vertices $v$ in that tree using the maximum path length $p$ and a maximum degree that applies to all vertices $d$. Assuming that I drew my test tree ...
3
votes
0answers
119 views

Quantities measuring the sparseness of a graph and of a matrix?

What are some quantities often used to measure the sparseness of a graph? For example, in a graph, with the number of vertices fixed, the smaller the maximum degree is, the more sparse the graph is. ...
2
votes
1answer
124 views

Having a forest and making it into a tree?

Let F be a forest with 100 vertices and 90 edges. How many new edges must be added without adding vertices to obtain a tree? This is what I have so far for this question... I don't think it's this ...
2
votes
2answers
109 views

graph theory /combinatorics committee existence

I'm having trouble figuring out the problem below. I've laid out my approach and it seems combinatorics formulas might help solve this. If anyone can point to me to the right direction i would greatly ...
0
votes
0answers
787 views

Meanings of expansion and expander?

From Wikipedia Intuitively, an expander is a finite, undirected multigraph in which every subset of the vertices "which is not too large" has a "large" boundary. Different formalisations of ...
1
vote
1answer
3k views

Algorithm to check whether a graph has no cycles

Let $G=(V,E)$ be an undirected graph. Design an algorithm which decides whether the graph contains a cycle and proove its correctness and determine its complexity in terms of ...
0
votes
2answers
433 views

Vertex Cover degree problem

So Vertex cover (VC): Instance: a graph $G$ and an integer $k>0$. Question: Does $G$ have a vertex cover of size at most $k$? We will now define a version of this problem in which we assume that ...
0
votes
3answers
2k views

Isomorphism between two particular graphs

Are these two graphs isomorphic?
7
votes
2answers
1k views

Even cycles in a graph

I'm at a dead end with the following question, It seems simple enough but I cant seem to see it. Let G be a simple undirected graph with minimal degree 3, show that G contains an even cycle. Thanks. ...
77
votes
1answer
2k views

Number of simple edge-disjoint paths needed to cover a planar graph

Let $G=(V,E)$ be a graph with $|E|=m$ of a graph class $\mathcal{G}$. A path-cover $\mathcal{P}=\{P_1,\ldots,P_k\}$ is a partition of $E$ into edge-disjoint simple paths. The size of the cover is ...
0
votes
1answer
79 views

Graph theory: Determining $k$ from the chromatic polynomial

I know how to work out the chromatic polynomial of a graph and I can work out what $k$ would be by looking at the graph. Maybe I'm just being silly, but if you were given just the chromatic polynomial ...
8
votes
1answer
161 views

Does there always exist such a convex hull?

Suppose that $v_{1}$, $v_{2}$, $\ldots$,, $v_{2k}$ are $2k$ points in the plane. Is is true that there is always a convex hull of a subset of the $2k$ points such that at least $k$ of the $2k$ points ...
0
votes
2answers
249 views

Discrete Math Construct Tree from Weights

Consider the weights: 10, 12, 13, 16, 17, 17. (a) Construct an optimal coding scheme for the weights given by using a tree. (b) What is the total weight of the tree you found in part (a)?
4
votes
2answers
668 views

Planar and non-planar graphs, and Kuratowski's Theorem

A graph $G$ is planar if and only if every subdivision of $G$ is planar. A graph $G$ is planar if and only if it contains no subdivision of $K_{3,3}$ or $K_5$. A subdivision of an edge ...
0
votes
0answers
70 views

Abbreviations in Combinatorial Graph/Matrix theory

I'm getting started with research in combinatorics. I have come across a reference that uses a great deal of abbreviations. I was able to figure most of them out but there are a few that I can find. ...
2
votes
1answer
518 views

Pigeonhole Principle on Graphs

I just have a last minute question for my combinatorics final (which is in one hour!!). My prof particularly told me to study the following question and I'm pretty sure it involves the pigeonhole ...
4
votes
1answer
255 views

Triangle free graphs with large chromatic number

I am trying to understand the proof of Theorem 2 given here. (Page 5) The theorem states that $\forall k\exists$ a triangle free graph $G$ with $\chi(G)>k$. The proof constructs such a $G$ as ...
1
vote
1answer
519 views

$G$ connected planar graph, less than 12 vertices, then $\chi (G) \leq 4$

The problem is: Let $G$ be a connected planar graph with less than 12 vertices. a) Prove that G has a vertex with degree $\leq 4$. b) Prove that $\chi (G) \leq 4$. (Do not use the Four Color Theorem) ...
4
votes
0answers
454 views

Planar graphs with $n \geq 2$ vertices have at least two vertices whose degree is at most 5

This is a homework problem and my solution. To me I think I get the main ideas and understand what is going on but I need work on my proof writing I think as I don't get full credit when I think I ...
3
votes
1answer
2k views

Inductive Proof of Euler's Formula $v-e+r=2$

I'm just studying for finals here. My professor told me that there would be an inductive proof on the final, and I've never done one before. He told me a good sample problem was to prove Euler's ...
1
vote
2answers
270 views

Is it true that if a graph is n-regular that it must have n+1 vertices?

In other words if a graph is 3-regular does it need to have 4 vertices? I ask because I have been asked to prove that if $n$ is an odd number and $G$ is an $n$-regular graph that $G$ must have an ...
1
vote
1answer
200 views

$G$, a graph, $k$-color-critical $\Rightarrow$ $G$ is connected

We let $G$ be a graph which is $k$-color-critical, meaning $\chi (G) = k$ and removing any vertex results in a graph with a smaller chromatic number. My attempt has been to suppose that the graph $G$ ...
3
votes
1answer
283 views

Amalgamation of graphs

I am trying to understand the definition of amalgamation of a $n+1$-partite graph as explained here(first few lines of page 4). We have a $n+1$-partite graph $G$ with partite sets $V_0,V_1,\cdots,V_n$ ...
2
votes
2answers
721 views

If $n$ is a natural number $\ge 2$ how do I prove that any graph with $n$ vertices has at least two vertices of the same degree?

Any help would be appreciated. If $n$ is a natural number $\ge 2$ how do I prove that any graph with $n$ vertices has at least two vertices of the same degree?
1
vote
3answers
249 views

Non-isomorphic connected graphs question

How do I find all of the non-isomorphic connected graphs with the degree sequence 233345?
2
votes
2answers
678 views

Planar Graphs with at least $2$ vertices and degrees at most $5$

I'm trying to study for my combinatorics exam and this was a suggested problem. Let $G$ be a planar graph on $V\geq 2$ vertices. How can we prove that $G$ has at least $2$ vertices whose degrees are ...
1
vote
2answers
668 views

Chromatic Polynomial

I am asked the following: Let n be a positive integer at least 3. The wheel W_n is the graph obtained by taking the cycle C_n, placing an additional vertex at the center, and joining it to ...
5
votes
4answers
659 views

Find cycles in graphs which do not contain other cycles

Intro: I'm working on a real-world engineering problem that can be translated to an undirected graph. I'm an aerospace engineer, so perhaps I don't know/use the correct mathematical terms to describe ...
5
votes
1answer
1k views

Why can't reachability be expressed in first order logic?

I'm wondering why we can't express graph reachability in first order logic in pretty much exactly the same way we express it in second order existential logic. For SOL, one definition is : 1 . L is ...
3
votes
1answer
4k views

How to draw Hasse diagram for divisibilty?

Please help me out.. Is there some appropriate method to draw Hasse diagram My question is $L=\{1,2,3,4,5,6,10,12,15,30,60\}$ Please explain me by step by step solution... Thanks for help..